Search NASA⌕ Search

SEARCH · Search NASA

Results for “linear solver”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 685 records · Page 38

A Simple, Scalable Large Deformation Solid Mechanics Implementation in the MOOSE Framework

This article describes a large deformation solid mechanics solver implemented as part of the freely available and open source MOOSE finite element simulation framework. The article documents the choices made in developing the solid mechanics framework and describes novel formulations for the gradient operator and constitutive modeling framework made to simplify implementations of different coordinate systems, stabilized gradient operators, and different constitutive model inputs and outputs. In the process, the article describes a new formulation that casts objective integration of the Cauchy stress as a linear transformation of the small stress rate. Finally, the article presents key implementation details and examines the parallel efficiency of the solid mechanics solver implemented in MOOSE. The implementation retains a good weak scaling efficiency beyond 1,000 parallel processes. The article includes a discussion of the factors limiting the parallel efficiency of implicit, large deformation solid mechanics codes on current high-performance computers, with the main current limitation being the scalability of the algebraic multigrid methods used to solve the linearized equilibrium equations.

Applied computing → Computer-aided design↗

Towards large-scale quantum optimization solvers with few qubits

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over $m={{\mathcal{O}}}({n}^{k})$ binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m , respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A stable partitioned FSI algorithm for incompressible flow and deforming beams

An added-mass partitioned (AMP) algorithm is described for solving fluid–structure interaction (FSI) problems coupling incompressible flows with thin elastic structures undergoing finite deformations. The new AMP scheme is fully second-order accurate and stable, without sub-time-step iterations, even for very light structures when added-mass effects are strong. The fluid, governed by the incompressible Navier–Stokes equations, is solved in velocity-pressure form using a fractional-step method; large deformations are treated with a mixed Eulerian-Lagrangian approach on deforming composite grids. The motion of the thin structure is governed by a generalized Euler–Bernoulli beam model, and these equations are solved in a Lagrangian frame using two approaches, one based on finite differences and the other on finite elements. The key AMP interface condition is a generalized Robin (mixed) condition on the fluid pressure. This condition, which is derived at a continuous level, has no adjustable parameters and is applied at the discrete level to couple the partitioned domain solvers. Special treatment of the AMP condition is required to couple the finite-element beam solver with the finite-difference-based fluid solver, and two coupling approaches are described. A normal-mode stability analysis is performed for a linearized model problem involving a beam separating two fluid domains, and it is shown that the AMP scheme is stable independent of the ratio of the mass of the fluid to that of the structure. A traditional partitioned (TP) scheme using a Dirichlet–Neumann coupling for the same model problem is shown to be unconditionally unstable if the added mass of the fluid is too large. A series of benchmark problems of increasing complexity are considered to illustrate the behavior of the AMP algorithm, and to compare the behavior with that of the TP scheme. The results of all these benchmark problems verify the stability and accuracy of the AMP scheme. Results for one benchmark problem modeling blood flow in a deforming artery are also compared with corresponding results available in the literature.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Two-Level Adaptive Algebraic Multigrid for a Sequence of Problems with Slowly Varying Random Coefficients [Adaptive Algebraic Multigrid for Sequence of Problems with Slowly Varying Random Coefficients]

Our paper proposes an adaptive strategy for reusing a previously constructed coarse space by algebraic multigrid to construct a two-level solver for a problem with nearby characteristics. Furthermore, a main target application is the solution of the linear problems that appear throughout a sequence of Markov chain Monte Carlo simulations of subsurface flow with uncertain permeability field. We demonstrate the efficacy of the method with extensive set of numerical experiments.

97 MATHEMATICS AND COMPUTING↗

MueMat Multicrid Toolbox

MueMat is intended for the research and development of multigrid algorithms used in the solution of sparse linear systems arising from systems of partial differential equations. The software can generate example linear systems and provides short programs to demonstrate the various interfaces for creating, accessing, and applying the solvers. MueMat currently includes two types of algebraic multigrid methods and many commonly used smoothers. However, the software is intended to be extensible, and new methods can be incorporated easily. MueMat also allows for advanced usage, such as combining multiple methods and segregated solves. The library supports point and block access to matrix data. MueMat has been designed for use within the programming environment of the Mathworks program MATLAB®. All algorithms and methods in MueMat have been or will be published in the open scientific literature.

Boman, ErikG.↗

Alternative mixed integer linear programming optimization for joint job scheduling and data allocation in grid computing

This paper presents a novel approach to the joint optimization of job scheduling and data allocation in grid computing environments. We formulate this joint optimization problem as a mixed integer quadratically constrained program. To tackle the nonlinearity in the constraint, we alternatively fix a subset of decision variables and optimize the remaining ones via Mixed Integer Linear Programming (MILP). We solve the MILP problem at each iteration via an off-the-shelf MILP solver. Our experimental results show that our method significantly outperforms existing heuristic methods, employing either independent optimization or joint optimization strategies. We have also verified the generalization ability of our method over grid environments with various sizes and its high robustness to the algorithm setting.

97 MATHEMATICS AND COMPUTING↗

On the Strong Scaling of the Spectral Element Solver Nek5000 on Petascale Systems. In: EASC '16 Proceedings of the Exascale Applications and Software Conference 2016, Article No. 5

The present work is targeted at performing a strong scaling study of the high-order spectral element fluid dynamics solver Nek5000. Prior studies such as [5] indicated a recommendable metric for strong scalability from a theoretical viewpoint, which we test here extensively on three parallel machines with different performance characteristics and interconnect networks, namely Mira (IBM Blue Gene/Q), Beskow (Cray XC40) and Titan (Cray XK7). The test cases considered for the simulations correspond to a turbulent flow in a straight pipe at four different friction Reynolds numbers Reτ = 180, 360, 550 and 1000. Considering the linear model for parallel communication we quantify the machine characteristics in order to better assess the scaling behaviors of the code. Subsequently sampling and profiling tools are used to measure the computation and communication times over a large range of compute cores. We also study the effect of the two coarse grid solvers XXT and AMG on the computational time. Super-linear scaling due to a reduction in cache misses is observed on each computer. The strong scaling limit is attained for roughly 5000-10,000 degrees of freedom per core on Mira, 30,000 - 50,0000 on Beskow, with only a small impact of the problem size for both machines, and ranges between 10,000 and 220,000 depending on the problem size on Titan. This work aims at being a reference for Nek5000 users and also serves as a basis for potential issues to address as the community heads towards exascale supercomputers.

Offermans, Nicolas↗

The General Atomics Center for Magnetohydrodynamic Modeling (CEMM) Final Report

The Center for Extended Magnetohydrodynamic Modeling (CEMM) is built around the further development, verification, validation, and other application of two major extended magnetohydrodynamics (MHD) codes NIMROD and M3D-C1. The General Atomics (GA) CEMM Program focuses on three main research areas: extension of the M3D-C1 MHD code plasma response calculations to new regimes, coupling of the DK4D drift kinetic equation solver to a temperature evolution equation, and simulations of disruption mitigation for unstable plasmas with pre-existing magnetic islands using massive gas injection (MGI) with the NIMROD MHD code. A systematic scan of the zero-crossing of the rotation profile in a DIII-D ITER-similar shape equilibrium using linear, time-independent modeling with M3D-C1 was performed. A new Python utility, autoC1, has been developed to automate the running of M3D-C1 for linear simulations. A number of ELM suppression experiments were analyzed including a validation and cross-code verification with the MARS-F MHD code of magnetic signal phase shifts across ELM-suppression bifurcations. A linearized, time-dependent temperature equation was tightly coupled to the electron and ion drift-kinetic equations (DKEs) in the DK4D drift-kinetic equation solver. Various explicit and implicit implementations were attempted, but all methods proved numerically unstable, even with the addition of numerical dissipation. Several simulations were completed investigating the effects of pre-existing islands on disruption mitigation by MGI in DIII-D using NIMROD.

3D MHD Simulation↗

Lattice Green’s Functions for High-Order Finite Difference Stencils

Lattice Green's Functions (LGFs) are fundamental solutions to discretized linear operators, and as such they are a useful tool for solving discretized elliptic PDEs on domains that are unbounded in one or more directions. The majority of existing numerical solvers that make use of LGFs rely on a second-order discretization and operate on domains with free-space boundary conditions in all directions. Under these conditions, fast expansion methods are available that enable precomputation of 2D or 3D LGFs in linear time, avoiding the need for brute-force multi-dimensional quadrature of numerically unstable integrals. Here we focus on higher-order discretizations of the Laplace operator on domains with more general boundary conditions, by (1) providing an algorithm for fast and accurate evaluation of the LGFs associated with high-order dimension-split centered finite differences on unbounded domains, and (2) deriving closed-form expressions for the LGFs associated with both dimension-split and Mehrstellen discretizations on domains with one unbounded dimension. Through numerical experiments we demonstrate that these techniques provide LGF evaluations with near machine-precision accuracy, and that the resulting LGFs allow for numerically consistent solutions to high-order discretizations of the Poisson's equation on fully or partially unbounded 3D domains.

97 MATHEMATICS AND COMPUTING↗

Algorithmically scalable block preconditioner for fully implicit shallow-water equations in CAM-SE

Performing accurate and efficient numerical simulation of global atmospheric climate models is challenging due to the disparate length and time scales over which physical processes interact. Implicit solvers enable the physical system to be integrated with a time step commensurate with processes being studied. The dominant cost of an implicit time step is the ancillary linear system solves, so we have developed a preconditioner aimed at improving the efficiency of these linear system solves. Our preconditioner is based on an approximate block factorization of the linearized shallow-water equations and has been implemented within the spectral element dynamical core within the Community Atmospheric Model (CAM-SE). Furthermore, in this paper we discuss the development and scalability of the preconditioner for a suite of test cases with the implicit shallow-water solver within CAM-SE.

97 MATHEMATICS AND COMPUTING↗

A Parallel Solver for Graph Laplacians

Problems from graph drawing, spectral clustering, network flow and graph partitioning can all be expressed in terms of graph Laplacian matrices. There are a variety of practical approaches to solving these problems in serial. However, as problem sizes increase and single core speeds stagnate, parallelism is essential to solve such problems quickly. We present an unsmoothed aggregation multigrid method for solving graph Laplacians in a distributed memory setting. We introduce new parallel aggregation and low degree elimination algorithms targeted specifically at irregular degree graphs. These algorithms are expressed in terms of sparse matrix-vector products using generalized sum and product operations. This formulation is amenable to linear algebra using arbitrary distributions and allows us to operate on a 2D sparse matrix distribution, which is necessary for parallel scalability. Our solver outperforms the natural parallel extension of the current state of the art in an algorithmic comparison. We demonstrate scalability to 576 processes and graphs with up to 1.7 billion edges.

Konolige, Tristan↗

SU-F-T-540: Comprehensive Fluence Delivery Optimization with Multileaf Collimation

Purpose: Multileaf collimator (MLC) leaf sequencing is performed via commercial black-box implementations, on which a user has limited to no access. We have developed an explicit, generic MLC sequencing model to serve as a tool for future investigations of fluence map optimization, fluence delivery optimization, and rotational collimator delivery methods. Methods: We have developed a novel, comprehensive model to effectively account for a variety of transmission and penumbra effects previously treated on an ad hoc basis in the literature. As the model is capable of quantifying a variety of effects, we utilize the asymmetric leakage intensity across each leaf to deliver fluence maps with pixel size smaller than the narrowest leaf width. Developed using linear programming and mixed integer programming formulations, the model is implemented using state of the art open-source solvers. To demonstrate the versatility of the algorithm, a graphical user interface (GUI) was developed in MATLAB capable of accepting custom leaf specifications and transmission parameters. As a preliminary proof-ofconcept, we have sequenced the leaves of a Varian 120 Leaf Millennium MLC for five prostate cancer patient fields and one head and neck field. Predetermined fluence maps have been processed by data smoothing methods to obtain pixel sizes of 2.5 cm{sup 2}. The quality of output was analyzed using computer simulations. Results: For the prostate fields, an average root mean squared error (RMSE) of 0.82 and gamma (0.5mm/0.5%) of 91.4% were observed compared to RMSE and gamma (0.5mm/0.5%) values of 7.04 and 34.0% when the leakage considerations were omitted. Similar results were observed for the head and neck case. Conclusion: A model to sequence MLC leaves to optimality has been proposed. Future work will involve extensive testing and evaluation of the method on clinical MLCs and comparison with black-box leaf sequencing algorithms currently used by commercial treatment planning systems.

60 APPLIED LIFE SCIENCES↗

Reliable and efficient solution of genome-scale models of Metabolism and macromolecular Expression

Currently, Constraint-Based Reconstruction and Analysis (COBRA) is the only methodology that permits integrated modeling of Metabolism and macromolecular Expression (ME) at genome-scale. Linear optimization computes steady-state flux solutions to ME models, but flux values are spread over many orders of magnitude. Data values also have greatly varying magnitudes. Furthermore, standard double-precision solvers may return inaccurate solutions or report that no solution exists. Exact simplex solvers based on rational arithmetic require a near-optimal warm start to be practical on large problems (current ME models have 70,000 constraints and variables and will grow larger). We also developed a quadrupleprecision version of our linear and nonlinear optimizer MINOS, and a solution procedure (DQQ) involving Double and Quad MINOS that achieves reliability and efficiency for ME models and other challenging problems tested here. DQQ will enable extensive use of large linear and nonlinear models in systems biology and other applications involving multiscale data.

59 BASIC BIOLOGICAL SCIENCES↗

Fast solvers for tokamak fluid models with PETSc

Multigrid (MG) is widely recognized as a highly effective solver for the model problem, the Laplacian, but textbook MG fails on most problems of interest. MG methods have been applied to complex, real-world applications with careful consideration of the physical model and discretization. In this work we develop the first step in applying MG methods to science and engineering relevant magnetohydrodynamics (MHD) tokamak models in the M3D-C1 (https://m3dc1.pppl.gov) fusion energy science code. The semi-implicit time integrator in M3D-C1 is composed of many linear solves. The implicit advance of the momentum equation is the most challenging and is the focus of this work. The current production solver in M3D-C1 is a block Jacobi (BJ) preconditioner within a Krylov solver, where blocks group degrees of freedom on planes of constant toroidal coordinate. BJ convergence degrades as the number of planes increases due to the spectral properties of the matrix preconditioned with BJ. The partially magnetic field-aligned, regular toroidal grid structure in M3D-C1 is amenable to semi-coarsening geometric MG in the toroidal direction. This paper develops such a solver and demonstrates competitive performance on a runaway electron model of a SPARC (https://cfs.energy/technology/sparc) disruption, and superior robustness on a stellarator model on which the BJ solver fails to converge.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

SU-G-TeP1-15: Toward a Novel GPU Accelerated Deterministic Solution to the Linear Boltzmann Transport Equation

Purpose: To develop a Graphic Processor Unit (GPU) accelerated deterministic solution to the Linear Boltzmann Transport Equation (LBTE) for accurate dose calculations in radiotherapy (RT). A deterministic solution yields the potential for major speed improvements due to the sparse matrix-vector and vector-vector multiplications and would thus be of benefit to RT. Methods: In order to leverage the massively parallel architecture of GPUs, the first order LBTE was reformulated as a second order self-adjoint equation using the Least Squares Finite Element Method (LSFEM). This produces a symmetric positive-definite matrix which is efficiently solved using a parallelized conjugate gradient (CG) solver. The LSFEM formalism is applied in space, discrete ordinates is applied in angle, and the Multigroup method is applied in energy. The final linear system of equations produced is tightly coupled in space and angle. Our code written in CUDA-C was benchmarked on an Nvidia GeForce TITAN-X GPU against an Intel i7-6700K CPU. A spatial mesh of 30,950 tetrahedral elements was used with an S4 angular approximation. Results: To avoid repeating a full computationally intensive finite element matrix assembly at each Multigroup energy, a novel mapping algorithm was developed which minimized the operations required at each energy. Additionally, a parallelized memory mapping for the kronecker product between the sparse spatial and angular matrices, including Dirichlet boundary conditions, was created. Atomicity is preserved by graph-coloring overlapping nodes into separate kernel launches. The one-time mapping calculations for matrix assembly, kronecker product, and boundary condition application took 452±1ms on GPU. Matrix assembly for 16 energy groups took 556±3s on CPU, and 358±2ms on GPU using the mappings developed. The CG solver took 93±1s on CPU, and 468±2ms on GPU. Conclusion: Three computationally intensive subroutines in deterministically solving the LBTE have been formulated on GPU, resulting in two orders of magnitude speedup. Funding support from Natural Sciences and Engineering Research Council and Alberta Innovates Health Solutions. Dr. Fallone is a co-founder and CEO of MagnetTx Oncology Solutions (under discussions to license Alberta bi-planar linac MR for commercialization).

60 APPLIED LIFE SCIENCES↗

Kinetic-j : A computational kernel for solving the linearized Vlasov equation applied to calculations of the kinetic, configuration space plasma current for time harmonic wave electric fields

We present the Kinetic-j code, a computational kernel for evaluating the linearized Vlasov equation withapplication to calculating the kinetic plasma response (current) to an applied time harmonic wave electricfield. This code addresses the need for a configuration space evaluation of the plasma current to enablekinetic full-wave solvers for waves in hot plasmas to move beyond the limitations of the traditional Fourierspectral methods. We benchmark the kernel via comparison with the standard k-space forms of the hotplasma conductivity tensor.

Green, David L.↗

Self-consistent solution of cosmological radiation-hydrodynamics and chemical ionization

We consider a PDE system comprising compressible hydrodynamics, flux-limited diffusion radiation transport and chemical ionization kinetics in a cosmologically-expanding universe. Under an operator-split framework, the cosmological hydrodynamics equations are solved through the piecewise parabolic method, as implemented in the Enzo community hydrodynamics code. The remainder of the model, including radiation transport, chemical ionization kinetics, and gas energy feedback, form a stiff coupled PDE system, which we solve using a fully-implicit inexact Newton approach, and which forms the crux of this paper. The inner linear Newton systems are solved using a Schur complement formulation, and employ a multigrid-preconditioned conjugate gradient solver for the inner Schur systems. We describe this approach and provide results on a suite of test problems, demonstrating its accuracy, robustness, and scalability to very large problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A High-Order Low-Order Algorithm with Exponentially Convergent Monte Carlo for Thermal Radiative Transfer

In this paper, we have implemented a new high-order low-order (HOLO) algorithm for solving thermal radiative transfer problems. The low-order (LO) system is based on the spatial and angular moments of the transport equation and a linear-discontinuous finite-element spatial representation, producing equations similar to the standard S 2 equations. The LO solver is fully implicit in time and efficiently resolves the nonlinear temperature dependence at each time step. The high-order (HO) solver utilizes exponentially convergent Monte Carlo (ECMC) to give a globally accurate solution for the angular intensity to a fixed-source pure-absorber transport problem. This global solution is used to compute consistency terms, which require the HO and LO solutions to converge toward the same solution. The use of ECMC allows for the efficient reduction of statistical noise in the Monte Carlo solution, reducing inaccuracies introduced through the LO consistency terms. Finally, we compare results with an implicit Monte Carlo code for one-dimensional gray test problems and demonstrate the efficiency of ECMC over standard Monte Carlo in this HOLO algorithm.

97 MATHEMATICS AND COMPUTING↗