Search NASA⌕ Search

SEARCH · Search NASA

Results for “Linear Equation 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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
DOE OSTI2018

Solving linear equations with messenger-field and conjugate gradient techniques: An application to CMB data analysis

We discuss linear system solvers invoking a messenger-field and compare them with (preconditioned) conjugate gradient approaches. We show that the messenger-field techniques correspond to fixed point iterations of an appropriately preconditioned initial system of linear equations. We then argue that a conjugate gradient solver applied to the same preconditioned system, or equivalently a preconditioned conjugate gradient solver using the same preconditioner and applied to the original system, will in general ensure at least a comparable and typically better performance in terms of the number of iterations to convergence and time-to-solution. We illustrate our conclusions with two common examples drawn from the cosmic microwave background (CMB) data analysis: Wiener filtering and map-making. In addition, and contrary to the standard lore in the CMB field, we show that the performance of the preconditioned conjugate gradient solver can depend significantly on the starting vector. In conclusion, this observation seems of particular importance in the cases of map-making of high signal-to-noise ratio sky maps and therefore should be of relevance for the next generation of CMB experiments.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2025

Hardware acceleration for HPS algorithms in two and three dimensions

We provide a flexible, open-source framework for hardware acceleration, namely massively-parallel execution on general-purpose graphics processing units (GPUs), applied to the hierarchical Poincaré–Steklov (HPS) family of algorithms for building fast direct solvers for linear elliptic partial differential equations. To take full advantage of the power of hardware acceleration, we propose two variants of HPS algorithms to improve performance on two- and three-dimensional problems. In the two-dimensional setting, we introduce a novel recomputation strategy that minimizes costly data transfers to and from the GPU; in three dimensions, we modify and extend the adaptive discretization technique of Geldermans and Gillman [1] to greatly reduce peak memory usage. We provide an open-source implementation of these methods written in JAX, a high-level accelerated linear algebra package, which allows for the first integration of a high-order fast direct solver with automatic differentiation tools. We conclude with extensive numerical examples showing our methods are fast and accurate on two- and three-dimensional problems.

Fast direct solvers↗
NASA NTRS1992

Complex generalized minimal residual algorithm for iterative solution of quantum-mechanical reactive scattering equations

Complex dense matrices corresponding to the D + H2 and O + HD reactions were solved using a complex generalized minimal residual (GMRes) algorithm described by Saad and Schultz (1986) and Saad (1990). To provide a test case with a different structure, the H + H2 system was also considered. It is shown that the computational effort for solutions with the GMRes algorithm depends on the dimension of the linear system, the total energy of the scattering problem, and the accuracy criterion. In several cases with dimensions in the range 1110-5632, the GMRes algorithm outperformed the LAPACK direct solver, with speedups for the linear equation solution as large as a factor of 23.

Chatfield, David C.↗
DOE OSTI2020

A fully implicit, scalable, conservative nonlinear relativistic Fokker–Planck 0D-2P solver for runaway electrons

Upon application of a sufficiently strong electric field, electrons break away from thermal equilibrium and approach relativistic speeds. These highly energetic ‘runaway’ electrons (~ MeV) play a significant role in tokamak disruption physics, and therefore their accurate understanding is essential to develop reliable mitigation strategies. As such, we have developed a fully implicit solver for the 0D-2P (i.e., including two momenta coordinates) relativistic nonlinear Fokker–Planck equation (rFP). As in earlier implicit rFP studies (NORSE, CQL3D), electron–ion interactions are modeled using the Lorentz operator, and synchrotron damping using the Abraham–Lorentz–Dirac reaction term. However, our implementation improves on these earlier studies by (1) ensuring exact conservation properties for electron collisions, (2) strictly preserving positivity, and (3) being scalable algorithmically and in parallel. Key to our proposed approach is an efficient multigrid preconditioner for the linearized rFP equation, a multigrid elliptic solver for the Braams–Karney potentials, and a novel adaptive technique to determine the associated boundary values. We verify the accuracy and efficiency of the proposed scheme with numerical results ranging from small electric-field electrical conductivity measurements to the accurate reproduction of runaway tail dynamics when strong electric fields are applied.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRS1976

Evaluation of out-of-core computer programs for the solution of symmetric banded linear equations

FORTRAN coded out-of-core equation solvers that solve using direct methods symmetric banded systems of simultaneous algebraic equations. Banded, frontal and column (skyline) solvers were studied as well as solvers that can partition the working area and thus could fit into any available core. Comparison timings are presented for several typical two dimensional and three dimensional continuum type grids of elements with and without midside nodes. Extensive conclusions are also given.

Dunham, R. S.↗
DOE OSTI2018

A Fast Solver for Implicit Integration of the Vlasov--Poisson System in the Eulerian Framework

In this paper, we present a domain decomposition algorithm to accelerate the solution of Eulerian-type discretizations of the linear, steady-state Vlasov equation. The steady-state solver then forms a key component in the implementation of fully implicit or nearly fully implicit temporal integrators for the nonlinear Vlasov--Poisson system. The solver relies on a particular decomposition of phase space that enables the use of sweeping techniques commonly used in radiation transport applications. The original linear system for the phase space unknowns is then replaced by a smaller linear system involving only unknowns on the boundary between subdomains, which can then be solved efficiently with Krylov methods such as GMRES. Steady-state solves are combined to form an implicit Runge--Kutta time integrator, and the Vlasov equation is coupled self-consistently to the Poisson equation via a linearized procedure or a nonlinear fixed-point method for the electric field. Finally, numerical results for standard test problems demonstrate the efficiency of the domain decomposition approach when compared to the direct application of an iterative solver to the original linear system.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2016

An Optimized Multicolor Point-Implicit Solver for Unstructured Grid Applications on Graphics Processing Units

In the field of computational fluid dynamics, the Navier-Stokes equations are often solved using an unstructuredgrid approach to accommodate geometric complexity. Implicit solution methodologies for such spatial discretizations generally require frequent solution of large tightly-coupled systems of block-sparse linear equations. The multicolor point-implicit solver used in the current work typically requires a significant fraction of the overall application run time. In this work, an efficient implementation of the solver for graphics processing units is proposed. Several factors present unique challenges to achieving an efficient implementation in this environment. These include the variable amount of parallelism available in different kernel calls, indirect memory access patterns, low arithmetic intensity, and the requirement to support variable block sizes. In this work, the solver is reformulated to use standard sparse and dense Basic Linear Algebra Subprograms (BLAS) functions. However, numerical experiments show that the performance of the BLAS functions available in existing CUDA libraries is suboptimal for matrices representative of those encountered in actual simulations. Instead, optimized versions of these functions are developed. Depending on block size, the new implementations show performance gains of up to 7x over the existing CUDA library functions.

Zubair, Mohammad↗
NASA NTRS1993

High resolution numerical simulation of the linearized Euler equations in conservation law form

A linearized Euler solver based on a high resolution numerical scheme is presented. The approach is to linearize the flux vector as opposed to carrying through the complete linearization analysis with the dependent variable vector written as a sum of the mean and the perturbed flow. This allows the linearized equations to be maintained in conservation law form. The linearized equations are used to compute unsteady flows in turbomachinery blade rows arising due to blade vibrations. Numerical solutions are compared to theoretical results (where available) and to numerical solutions of the nonlinear Euler equations.

Sreenivas, Kidambi↗
DOE OSTI2022

On the Response of a Herschel–Bulkley Fluid Due to a Moving Plate

In this paper, we study the boundary-layer flow of a Herschel–Bulkley fluid due to a moving plate; this problem has been experimentally investigated by others, where the fluid was assumed to be Carbopol, which has similar properties to cement. The computational fluid dynamics finite volume method from the open-source toolbox/library OpenFOAM is used on structured quad grids to solve the mass and the linear momentum conservation equations using the solver “overInterDyMFoam” customized with non-Newtonian viscosity libraries. The governing equations are solved numerically by using regularization methods in the context of the overset meshing technique. The results indicate that there is a good comparison between the experimental data and the simulations. The boundary layer thicknesses are predicted within the uncertainties of the measurements. The simulations indicate strong sensitivities to the rheological properties of the fluid.

36 MATERIALS SCIENCE↗
NASA NTRS1993

Three-dimensional unstructured grid Euler computations using a fully-implicit, upwind method

A method has been developed to solve the Euler equations on a three-dimensional unstructured grid composed of tetrahedra. The method uses an upwind flow solver with a linearized, backward-Euler time integration scheme. Each time step results in a sparse linear system of equations which is solved by an iterative, sparse matrix solver. Local-time stepping, switched evolution relaxation (SER), preconditioning and reuse of the Jacobian are employed to accelerate the convergence rate. Implicit boundary conditions were found to be extremely important for fast convergence. Numerical experiments have shown that convergence rates comparable to that of a multigrid, central-difference scheme are achievable on the same mesh. Results are presented for several grids about an ONERA M6 wing.

Whitaker, David L.↗
NASA NTRS2000

Three-Dimensional Nacelle Aeroacoustics Code With Application to Impedance Education

A three-dimensional nacelle acoustics code that accounts for uniform mean flow and variable surface impedance liners is developed. The code is linked to a commercial version of the NASA-developed General Purpose Solver (for solution of linear systems of equations) in order to obtain the capability to study high frequency waves that may require millions of grid points for resolution. Detailed, single-processor statistics for the performance of the solver in rigid and soft-wall ducts are presented. Over the range of frequencies of current interest in nacelle liner research, noise attenuation levels predicted from the code were in excellent agreement with those predicted from mode theory. The equation solver is memory efficient, requiring only a small fraction of the memory available on modern computers. As an application, the code is combined with an optimization algorithm and used to reduce the impedance spectrum of a ceramic liner. The primary problem with using the code to perform optimization studies at frequencies above I1kHz is the excessive CPU time (a major portion of which is matrix assembly). The research recommends that research be directed toward development of a rapid sparse assembler and exploitation of the multiprocessor capability of the solver to further reduce CPU time.

Watson, Willie R.↗
NASA NTRS1977

A block iterative LU solver for weakly coupled linear systems

A hybrid technique, called the block iterative LU solver, is proposed for solving the linear equations resulting from a finite element numerical analysis of certain fluid dynamics problems where the equations are weakly coupled between distinct sets of variables. Either the block Jacobi iterative method or the block Gauss-Seidel iterative solver is combined with LU decomposition.

Cooke, C. H.↗
DOE OSTI2023

JuliaOceanWaves

SAND2023-05107O JuliaOceanWaves is a collection of packages and functions for modeling wave energy converters. The open-source software is designed to be used by the wave energy community to model new concepts, perform design optimization, and more. Capabilities include: • A representation of ocean wave spectra and input/output (e.g. read from National Oceanic and Atmospheric Administration buoys) and post-processing functionalities; • A solver for the linear potential flow radiation and diffraction equations for wave forcing on floating structures. • Solving the floating body linear dynamics in the frequency domain. Future additions to the software will include solving non-linear floating body dynamics in the time-domain through time-marching Ordinary Differential Equation solvers and the pseudo-spectral optimization method. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

Michelen Strofer, Carlos↗
DOE OSTI2022

MAPPRAISER: A massively parallel map-making framework for multi-kilo pixel CMB experiments

Forthcoming cosmic microwave background (CMB) polarized anisotropy experiments have the potential to revolutionize our understanding of the Universe and fundamental physics. The sought-after, tale-telling signatures will be however distributed over voluminous data sets which these experiments will collect. These data sets will need to be efficiently processed and unwanted contributions due to astrophysical, environmental, and instrumental effects characterized and efficiently mitigated in order to uncover the signatures. This poses a significant challenge to data analysis methods, techniques, and software tools which will not only have to be able to cope with huge volumes of data but to do so with unprecedented precision driven by the demanding science goals posed for the new experiments. A keystone of efficient CMB data analysis is solvers of very large linear systems of equations. Such systems appear in very diverse contexts throughout CMB data analysis pipelines, however they typically display similar algebraic structures and can therefore be solved using similar numerical techniques. Linear systems arising in the so-called map-making problem are one of the most prominent and common ones. In this work we present a massively parallel, flexible and extensible framework, comprised of a numerical library, MIDAPACK, and a high level code, MAPPRAISER, which provide tools for solving efficiently such systems. Here, the framework implements iterative solvers based on conjugate gradient techniques: enlarged and preconditioned using different preconditioners. We demonstrate the framework on simulated examples reflecting basic characteristics of the forthcoming data sets issued by ground-based and satellite-borne instruments, executing it on as many as 16,384 compute cores. The software is developed as an open source project freely available to the community at: https://github.com/B3Dcmb/midapack.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2023

Variational Quantum Linear Solver

Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the re quired circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare |x$\rangle$ such that A|x$\rangle$ ∝ |b$\rangle$. We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision ϵ is achieved. Specifically, we prove that C $⩾$ ϵ 2 /κ 2 , where C is the VQLS cost function and κ is the condition number of A. We present efficient quantum circuits to estimate C, while providing evidence for the classical hardness of its estimation. Using Rigetti’s quantum computer, we success fully implement VQLS up to a problem size of 1024 × 1024. Finally, we numerically solve nontrivial problems of size up to 2 50 × 2 50 . For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in ϵ, κ, and the system size N.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2023

Terrain-Influenced Winds and Fire-Fire Interactions in Wildland Fire Simulations [Dissertation]

Ensemble-based approaches to prescribed fire planning cannot be supported by computational fluid dynamics based models like FIRETEC and the Wildland-Urban Interface Fire Dynamics Simulator (WFDS) because they are too computationally expensive and cannot leverage large eddy simulation approaches like CAWFE and WRF-SFIRE because they have too coarse of resolution. QUIC-Fire was developed to fill this gap but it cannot currently address complex terrain, that is typical for instance in the Western United States. This dissertation describes a variety of improvements made to QUIC-Fire and its various incorporated algorithms in an effort to make it a viable tool in simulating wildland and prescribed fires on terrain. The modifications made to QUIC-Fire are described in three chapters. The first chapter describes the extension of the diagnostic wind model QUIC-URB, the wind engine of QUIC-Fire, to a terrain-following coordinate system. The terraininfluenced winds it generates are analyzed and compared. In particular, this chapter presents the mathematical derivation of the wind solver leading to a linear system of equations that are solved through the successive over-relaxation method. The model is validated against a standard test used in previous works (the Askervein Hill) and against a new dataset from measurements in the Socorro Mountains, New Mexico. The terrain-following implementation captures the correct phenomenology for the isolated Askervein Hill, with a wind speed up at the top of the hill. The model agrees well with measurements on the upwind side of the peak, but overestimates speed-up on the downwind side of the hill. This is due to the inability of the model to generate flow separation and wake-eddy dynamics. On a common laptop, the divergence-free wind field is obtained in 6 s, making the solver appealing for coupled fire-atmosphere simulations. The Socorro Mountain is highly complex, with many cliff faces, peaks, and valleys. Although the model captures the magnitude and direction of inlet and outlet areas of the domain, it performs rather poorly in the valley region and in the regions near the steep cliffs. Hence, the model shows good agreement with data in areas of open sloped terrain but lacks in areas where flow separation and thermally driven effects may be present (neither effect is addressed in this work). In the second chapter the implementation of the terrain-following version of QUIC-URB into QUIC-Fire, and the necessary changes needed to include terrain are described. No changes to the underlying fire spread algorithm are made other than what is required to correctly account for the inclusion of terrain. Previously published FIRETEC results that use five different topographies that share the same centerline profile are compared to simulation results from the modified QUIC-Fire that use the same topographies and fuels. QUIC-Fire results show overall similar behaviors in terms of how the topographies affect fire shapes and trends in spread rates. Due to the terrain-following version of QUIC-URB being unable to generate flow separations at the crest of hills, fire spread rates in these regions across all topographies are over-predicted when compared to FIRETEC. Lateral fire growth shows similar trends with FIRETEC between topographies but does not capture the increase in spread due to a diagonal interface between grassland and forested fuel region of the domain. These results suggest that there are three algorithms within QUIC-Fire that could use improvement: how flame tilt angle is accounted for, the incorporation of non-local drag effects, and the inclusion of the wake-eddy parameterizations that are used in QUIC-URB. Lastly, the third chapter describes a modification to the initial guess used for the calculation of the QUIC-URB mass-conserved wind solution during fire simulations. The modification is aimed at improving fire-fire interactions in QUIC-Fire simulations. The modification consists of using the solution from the previous timestep as the starting point for the calculation of the solution for the next timestep. Fire-fire interactions is greatly improved by the change but a new source of error is introduced. Due to how plumes are modelled in QUIC-Fire the new solution contains errors where gaps in the plume structure are present. However, these errors are mostly limited to the upper atmosphere, where they do not affect fire behavior at the surface, and their magnitude isn’t significant enough to discount the amount of new fire phenomenology now captured in QUIC-Fire with the change.

58 GEOSCIENCES↗
DOE OSTI2022

QUIC-URB and QUIC-fire extension to complex terrain: Development of a terrain-following coordinate system

Ensemble-based approaches to prescribed fire planning cannot be supported by CFD-based models like FIRETEC and WFDS because they are too computationally expensive and cannot leverage LES approaches like CAWFE and WRF-SFIRE because too coarse of resolution. QUIC-Fire was developed to fill this gap but it cannot currently address complex terrain, typical for instance of the Western United States. In this paper, we describe the extension of the diagnostic wind model QUIC-URB, the wind engine of QUIC-Fire, to a terrain-following coordinate system. In particular, the paper presents the mathematical derivation of the wind solver leading to a linear system of equations that are solved through the successive over-relaxation method. The model is validated against a standard test used in previous works (the Askervein Hill) and against a new dataset from measurements in the Socorro Mountains, New Mexico. The terrain-following implementation captured the correct phenomenology for the isolated Askervein Hill, with a wind speed up at the top of the hill. We report the model agreed well with measurements on the upwind side of the peak, but overestimated speed-up on the downwind side of the hill. This is due to the inability of the model to generate flow separation and wake-eddy dynamics. On a common laptop, the divergence-free wind field was obtained in 6 s, making the solver appealing for coupled fire–atmosphere simulations. The Socorro Mountain was highly complex, with many cliff faces, peaks, and valleys. Although the model captures the magnitude and direction of inlet and outlet areas of the domain, it performs rather poorly in the valley region and in the regions near the steep cliffs. Hence, the model shows good agreement with data in areas of open sloped terrain but lacks in areas where flow separation and thermally driven effects may be present (neither effect was addressed in this work). Results highlight that future work should focus on the implementation of parameterizations of wake-eddies, similar to QUIC-URB’s building parameterizations, and on thermodynamic-driven flow.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2015

A third-order implicit discontinuous Galerkin method based on a Hermite WENO reconstruction for time-accurate solution of the compressible Navier-Stokes equations

Here, a space and time third-order discontinuous Galerkin method based on a Hermite weighted essentially non-oscillatory reconstruction is presented for the unsteady compressible Euler and Navier–Stokes equations. At each time step, a lower-upper symmetric Gauss–Seidel preconditioned generalized minimal residual solver is used to solve the systems of linear equations arising from an explicit first stage, single diagonal coefficient, diagonally implicit Runge–Kutta time integration scheme. The performance of the developed method is assessed through a variety of unsteady flow problems. Numerical results indicate that this method is able to deliver the designed third-order accuracy of convergence in both space and time, while requiring remarkably less storage than the standard third-order discontinous Galerkin methods, and less computing time than the lower-order discontinous Galerkin methods to achieve the same level of temporal accuracy for computing unsteady flow problems.

97 MATHEMATICS AND COMPUTING↗