Search NASA⌕ Search

SEARCH · Search NASA

Results for “sparse 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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
NASA NTRS1989

Application of direct solvers to unstructured meshes for the Euler and Navier-Stokes equations using upwind schemes

The application of Newton iteration to inviscid and viscous airfoil calculations on unstructured meshes is examined. A cell-centered finite volume scheme is employed on an unstructured mesh consisting of triangles. Roe's flux difference splitting scheme is used to compute the inviscid fluxes. Higher order accuracy is achieved by an interpolation procedure that makes use of auxiliary gradients. The efficient solution of the sparse linear system of equations which arises upon linearization in time is addressed. Results are presented for inviscid and viscous test cases. The complications which arise due to the introduction of nonlinear limiters are addressed.

Venkatakrishnan, V.↗
DOE OSTI2018

Signal-Preserving Erratic Noise Attenuation via Iterative Robust Sparsity-Promoting Filter

Sparse domain thresholding filters operating in a sparse domain are highly effective in removing Gaussian random noise under Gaussian distribution assumption. Erratic noise, which designates non-Gaussian noise that consists of large isolated events with known or unknown distribution, also needs to be explicitly taken into account. However, conventional sparse domain thresholding filters based on the least-squares (LS) criterion are severely sensitive to data with high-amplitude and non-Gaussian noise, i.e., the erratic noise, which makes the suppression of this type of noise extremely challenging. Here, in this paper, we present a robust sparsity-promoting denoising model, in which the LS criterion is replaced by the Huber criterion to weaken the effects of erratic noise. The random and erratic noise is distinguished by using a data-adaptive parameter in the presented method, where random noise is described by mean square, while the erratic noise is downweighted through a damped weight. Different from conventional sparse domain thresholding filters, definition of the misfit between noisy data and recovered signal via the Huber criterion results in a nonlinear optimization problem. With the help of theoretical pseudoseismic data, an iterative robust sparsity-promoting filter is proposed to transform the nonlinear optimization problem into a linear LS problem through an iterative procedure. The main advantage of this transformation is that the nonlinear denoising filter can be solved by conventional LS solvers. Lastly, tests with several data sets demonstrate that the proposed denoising filter can successfully attenuate the erratic noise without damaging useful signal when compared with conventional denoising approaches based on the LS criterion.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1991

Implicit solvers for unstructured meshes

Implicit methods for unstructured mesh computations are developed and tested. The approximate system which arises from the Newton-linearization of the nonlinear evolution operator is solved by using the preconditioned generalized minimum residual technique. These different preconditioners are investigated: the incomplete LU factorization (ILU), block diagonal factorization, and the symmetric successive over-relaxation (SSOR). The preconditioners have been optimized to have good vectorization properties. The various methods are compared over a wide range of problems. Ordering of the unknowns, which affects the convergence of these sparse matrix iterative methods, is also investigated. Results are presented for inviscid and turbulent viscous calculations on single and multielement airfoil configurations using globally and adaptively generated meshes.

Venkatakrishnan, V.↗
NASA NTRS1992

An incremental strategy for calculating consistent discrete CFD sensitivity derivatives

In this preliminary study involving advanced computational fluid dynamic (CFD) codes, an incremental formulation, also known as the 'delta' or 'correction' form, is presented for solving the very large sparse systems of linear equations which are associated with aerodynamic sensitivity analysis. For typical problems in 2D, a direct solution method can be applied to these linear equations which are associated with aerodynamic sensitivity analysis. For typical problems in 2D, a direct solution method can be applied to these linear equations in either the standard or the incremental form, in which case the two are equivalent. Iterative methods appear to be needed for future 3D applications; however, because direct solver methods require much more computer memory than is currently available. Iterative methods for solving these equations in the standard form result in certain difficulties, such as ill-conditioning of the coefficient matrix, which can be overcome when these equations are cast in the incremental form; these and other benefits are discussed. The methodology is successfully implemented and tested in 2D using an upwind, cell-centered, finite volume formulation applied to the thin-layer Navier-Stokes equations. Results are presented for two laminar sample problems: (1) transonic flow through a double-throat nozzle; and (2) flow over an isolated airfoil.

Korivi, Vamshi Mohan↗
NASA NTRS1994

Parallel Preconditioning for CFD Problems on the CM-5

Up to today, preconditioning methods on massively parallel systems have faced a major difficulty. The most successful preconditioning methods in terms of accelerating the convergence of the iterative solver such as incomplete LU factorizations are notoriously difficult to implement on parallel machines for two reasons: (1) the actual computation of the preconditioner is not very floating-point intensive, but requires a large amount of unstructured communication, and (2) the application of the preconditioning matrix in the iteration phase (i.e. triangular solves) are difficult to parallelize because of the recursive nature of the computation. Here we present a new approach to preconditioning for very large, sparse, unsymmetric, linear systems, which avoids both difficulties. We explicitly compute an approximate inverse to our original matrix. This new preconditioning matrix can be applied most efficiently for iterative methods on massively parallel machines, since the preconditioning phase involves only a matrix-vector multiplication, with possibly a dense matrix. Furthermore the actual computation of the preconditioning matrix has natural parallelism. For a problem of size n, the preconditioning matrix can be computed by solving n independent small least squares problems. The algorithm and its implementation on the Connection Machine CM-5 are discussed in detail and supported by extensive timings obtained from real problem data.

Simon, Horst D.↗
NASA NTRS1991

Implicit solvers for unstructured meshes

Implicit methods were developed and tested for unstructured mesh computations. The approximate system which arises from the Newton linearization of the nonlinear evolution operator is solved by using the preconditioned GMRES (Generalized Minimum Residual) technique. Three different preconditioners were studied, namely, the incomplete LU factorization (ILU), block diagonal factorization, and the symmetric successive over relaxation (SSOR). The preconditioners were optimized to have good vectorization properties. SSOR and ILU were also studied as iterative schemes. The various methods are compared over a wide range of problems. Ordering of the unknowns, which affects the convergence of these sparse matrix iterative methods, is also studied. Results are presented for inviscid and turbulent viscous calculations on single and multielement airfoil configurations using globally and adaptively generated meshes.

Venkatakrishnan, V.↗
DOE OSTI2022

HyKKT: a hybrid direct-iterative method for solving KKT linear systems

Here, we propose a solution strategy for the large indefinite linear systems arising in interior methods for nonlinear optimization. The method is suitable for implementation on hardware accelerators such as graphical processing units (GPUs). The current gold standard for sparse indefinite systems is the LBLT factorization where L is a lower triangular matrix and B is 1×1 or 2×2 block diagonal. However, this requires pivoting, which substantially increases communication cost and degrades performance on GPUs. Our approach solves a large indefinite system by solving multiple smaller positive definite systems, using an iterative solver on the Schur complement and an inner direct solve (via Cholesky factorization) within each iteration. Cholesky is stable without pivoting, thereby reducing communication and allowing reuse of the symbolic factorization. We demonstrate the practicality of our approach on large optimal power flow problems and show that it can efficiently utilize GPUs and outperform LBL T factorization of the full system.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Block encoding of the three-dimensional heterogeneous Poisson equation with application to fracture flow

Quantum linear system (QLS) algorithms offer the potential to solve large-scale linear systems exponentially faster than classical methods. However, applying QLS algorithms to real-world problems remains challenging due to issues such as state preparation, data loading, and efficient information extraction. In this work, we study the feasibility of applying QLS algorithms to solve discretized three-dimensional (3D) heterogeneous Poisson equations, with specific examples relating to groundwater flow through geologic fracture networks. We explicitly construct a block encoding for the 3D heterogeneous Poisson matrix by leveraging the sparse local structure of the discretized operator. While classical solvers benefit from preconditioning, we show that block encoding the system matrix and preconditioner separately does not improve the effective condition number that dominates the QLS run-time. This differs from classical approaches where the preconditioner and the system matrix can often be implemented independently. Nevertheless, due to the structure of the problem in three dimensions, the quantum algorithm achieves a run-time of 𝑂⁡(𝑁 2/3 polylog 𝑁 ⋅log (1/𝜖)), outperforming the best classical methods (with run times of 𝑂⁡(𝑁⁢log 𝑁 ⋅log (1/𝜖))) and offering exponential memory savings. These results highlight both the promise and limitations of QLS algorithms for practical scientific computing, and point to effective condition-number reduction as a key barrier in achieving quantum advantages.

58 GEOSCIENCES↗
DOE OSTI2019

O(N) Quantum Molecular Dynamics (QMD) Algorithms, Code Requirements, Release Notes, and Library Deployment

The Exascale Computing Project (ECP) Co-design Center for Particle Applications (CoPA) is addressing the challenges for particle applications to run on upcoming exascale computing architectures. This includes short- and long-range molecular dynamics (MD), particle-in-cell (PIC), and quantum molecular dynamics (QMD). This document addresses $\mathcal{O}(N)$ QMD. The goal of this CoPA team is to develop $\mathcal{O}(N)$ linear scaling methods for QMD optimized for new and next generation architectures. This will provide the capability to simulate larger systems and run for longer timeframes than is possible today. Focus is initially on the density matrix construction. This requires efficient matrix formats and linear algebra operations for distributed architectures. A significant reduction in the wallclock time for an MD timestep is necessary to achieve practical large scale QMD. Equally challenging is to develop scalable distributed implementations. This requires the exploration of efficient data formats (dense, sparse, etc.), data decomposition and distribution across compute nodes using block- and graph-based methods. Traditional programming models such as MPI/OpenMP, hybrid MPI/OpenMP/Accelerator, as well as asynchronous task-based models will be explored to achieve maximum parallelism. Parallelism at the level of a matrix operation, solver, and/or application needs to be explored to gain the most benefit on new and emerging architectures. This report serves as a “living document” of the additions and enhancements throughout the ECP CoPA project for $\mathcal{O}(N)$ QMD. The following sections address the applications we are working with, the quantum chemistry libraries (BML and PROGRESS), and our co-design exploration through the use of a proxy application.

36 MATERIALS SCIENCE↗
NASA NTRSDate not supplied

Sparse Linear Algebra Toolkit for Computational Aerodynamics

Finding solutions to sparse linear systems of equations is an essential step in Computational Engineering applications of interest to NASA. Linear systems of equations are composed and solved in almost every computational engineering application. The characteristics of linear systems vary greatly from one application to another. Accordingly, there are a wide variety of methods for the solution of linear systems of equations. The operations and methods prepared by the authors are focused on linear systems of interest to NASA, primarily those associated with Computational Fluid Dynamics (CFD), Aeroelasticity, and Aeroacoustics. The Sparse Linear Algebra Toolkit (SLAT) is a coordinated collection of software featuring operations, methods, and data structures that are useful when solving sparse linear systems of equations on modern computer architectures. The implemented operations and methods are designed and tuned for parallelism in shared memory, in distributed memory, and across the hybrid combination of distributed-shared memory. The toolkit includes novel methods and implementations for modern architectures and facilitates development of new approaches for meeting NASA’s evolving computational engineering challenges using evolving computer architectures that are not available in vendor libraries. In this paper, significant features and interfaces within SLAT are presented and verified for simulations performed with NASA’s CFD solver, FUN3D. The runtime and scaling performance of the Generalized Minimum Residual (GMRES) method implemented in SLAT is analyzed for the linear subproblems within the solution of turbulent Navier-Stokes equations employed in the simulation of high-lift configurations. Prior to this work, the SPARSKIT GMRES implementation was the only Krylov subspace method available within FUN3D. A strong scaling study shows the SLAT GMRES implementation facilitates accurate Reynolds-averaged Navier-Stokes CFD solutions between 15% and 56% faster than the SPARSKIT GMRES implementation.

Stephen L Wood↗
DOE OSTI2018

Algebraic multigrid preconditioners for two-phase flow in porous media with phase transitions [Algebraic multigrid preconditioners for multiphase flow in porous media with phase transitions]

Multiphase flow is a critical process in a wide range of applications, including oil and gas recovery, carbon sequestration, and contaminant remediation. Numerical simulation of multiphase flow requires solving of a large, sparse linear system resulting from the discretization of the partial differential equations modeling the flow. In the case of multiphase multicomponent flow with miscible effect, this is a very challenging task. The problem becomes even more difficult if phase transitions are taken into account. A new approach to handle phase transitions is to formulate the system as a nonlinear complementarity problem (NCP). Unlike in the primary variable switching technique, the set of primary variables in this approach is fixed even when there is phase transition. Not only does this improve the robustness of the nonlinear solver, it opens up the possibility to use multigrid methods to solve the resulting linear system. The disadvantage of the complementarity approach, however, is that when a phase disappears, the linear system has the structure of a saddle point problem and becomes indefinite, and current algebraic multigrid (AMG) algorithms cannot be applied directly. In this study, we explore the effectiveness of a new multilevel strategy, based on the multigrid reduction technique, to deal with problems of this type. We demonstrate the effectiveness of the method through numerical results for the case of two-phase, two-component flow with phase appearance/disappearance. In conclusion, we also show that the strategy is efficient and scales optimally with problem size.

02 PETROLEUM↗
NASA NTRS1991

Development of a steady potential solver for use with linearized, unsteady aerodynamic analyses

A full potential steady flow solver (SFLOW) developed explicitly for use with an inviscid unsteady aerodynamic analysis (LINFLO) is described. The steady solver uses the nonconservative form of the nonlinear potential flow equations together with an implicit, least squares, finite difference approximation to solve for the steady flow field. The difference equations were developed on a composite mesh which consists of a C grid embedded in a rectilinear (H grid) cascade mesh. The composite mesh is capable of resolving blade to blade and far field phenomena on the H grid, while accurately resolving local phenomena on the C grid. The resulting system of algebraic equations is arranged in matrix form using a sparse matrix package and solved by Newton's method. Steady and unsteady results are presented for two cascade configurations: a high speed compressor and a turbine with high exit Mach number.

Hoyniak, Daniel↗
DOE OSTI2017

Scalable domain decomposition solvers for stochastic PDEs in high performance computing

Stochastic spectral finite element models of practical engineering systems may involve solutions of linear systems or linearized systems for non-linear problems with billions of unknowns. For stochastic modeling, it is therefore essential to design robust, parallel and scalable algorithms that can efficiently utilize high-performance computing to tackle such large-scale systems. Domain decomposition based iterative solvers can handle such systems. And though these algorithms exhibit excellent scalabilities, significant algorithmic and implementational challenges exist to extend them to solve extreme-scale stochastic systems using emerging computing platforms. Intrusive polynomial chaos expansion based domain decomposition algorithms are extended here to concurrently handle high resolution in both spatial and stochastic domains using an in-house implementation. Sparse iterative solvers with efficient preconditioners are employed to solve the resulting global and subdomain level local systems through multi-level iterative solvers. We also use parallel sparse matrix–vector operations to reduce the floating-point operations and memory requirements. Numerical and parallel scalabilities of these algorithms are presented for the diffusion equation having spatially varying diffusion coefficient modeled by a non-Gaussian stochastic process. Scalability of the solvers with respect to the number of random variables is also investigated.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRS1988

The solution of linear systems of equations with a structural analysis code on the NAS CRAY-2

Two methods for solving linear systems of equations on the NAS Cray-2 are described. One is a direct method; the other is an iterative method. Both methods exploit the architecture of the Cray-2, particularly the vectorization, and are aimed at structural analysis applications. To demonstrate and evaluate the methods, they were installed in a finite element structural analysis code denoted the Computational Structural Mechanics (CSM) Testbed. A description of the techniques used to integrate the two solvers into the Testbed is given. Storage schemes, memory requirements, operation counts, and reformatting procedures are discussed. Finally, results from the new methods are compared with results from the initial Testbed sparse Choleski equation solver for three structural analysis problems. The new direct solvers described achieve the highest computational rates of the methods compared. The new iterative methods are not able to achieve as high computation rates as the vectorized direct solvers but are best for well conditioned problems which require fewer iterations to converge to the solution.

Poole, Eugene L.↗
DOE OSTI2019

Sparse, iterative simulation methods for one-dimensional laminar flames

Sparse, iterative simulation methods for one-dimensional laminar flames are proposed. The resulting steady and unsteady flame solvers exploit approximate Jacobians to greatly reduce the computational cost associated with matrix operations. The constant, non-unity Lewis number assumption is introduced to further reduce the computational cost. The solvers are also parallelized to reduce time-to-solution on distributed memory computer systems. Computed laminar flame speeds and species profiles for a range of chemical mechanisms (from 10 to 2878 species) are compared against a well-validated commercial code and are found to be consistent within solver tolerances. The computation times of both the unsteady and steady solutions increase only linearly with the number of species, which is a significant improvement over the quadratic or cubic scaling of existing steady-state flame solvers. For the largest mechanism tested, the steady-state flame solver is two orders of magnitude faster than commonly-used codes. The use of an approximate Jacobian is shown to reduce the rate of convergence for the steady-state solver, but does not significantly affect the domain of convergence. The steady-state solver with approximate Jacobian is thus well suited for computationally efficient laminar flame speed sweeps with large kinetic mechanisms.

42 ENGINEERING↗
DOE OSTI2026

Active operator learning with predictive uncertainty quantification for partial differential equations

With the increased prevalence of neural operators being used to provide rapid solutions to partial differential equations (PDEs), understanding the accuracy of model predictions and the associated error levels is necessary for deploying reliable surrogate models in scientific applications. Existing uncertainty quantification (UQ) frameworks employ ensembles or Bayesian methods, which can incur substantial computational costs during both training and inference. Here, we propose a lightweight predictive UQ method tailored for Deep operator networks (DeepONets) that also generalizes to other operator networks. Numerical experiments on linear and nonlinear PDEs demonstrate that the framework’s uncertainty estimates are unbiased and provide accurate out-of-distribution uncertainty predictions with a sufficiently large training dataset. Our framework provides fast inference and uncertainty estimates that can efficiently drive outer-loop analyses that would be prohibitively expensive with conventional solvers. We demonstrate how predictive uncertainties can be used in the context of Bayesian optimization and active learning problems to yield improvements in accuracy and data-efficiency for outer-loop optimization procedures. In the active learning setup, we extend the framework to Fourier Neural Operators (FNO) and describe a generalized method for other operator networks. To enable real-time deployment, we introduce an inference strategy based on precomputed trunk outputs and a sparse placement matrix, reducing evaluation time by more than a factor of five. Our method provides a practical route to uncertainty-aware operator learning in time-sensitive settings.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Initial CEED API (CEED-MS10)

Key components of CEED software development involve fast finite element operator storage and evaluation, architecture optimizations, performant algorithms for all orders, global kernels for finite element operators, efficient use of the memory sub-system, optimal data locality and motion, enhanced scalability and parallelism, and fast tensor contractions. As ultimate goals of the project, CEED is exploring and identifying the best algorithms for the full range of discretizations and applying algorithmic and software development to support ECP applications’ needs. In this milestone, we initiated the development and implementation of a common CEED API consisting of two main components: low-level and high-level APIs. We accomplished the goal of having the low-level component ready for the release of CEED v1.0 in the next quarter, see CEED-MS13. In this report we also provide a highlight from CEED’s integration with the MARBL app and the corresponding Laghos miniapp. A main theme in this work has been the systematic transition of advanced algorithms, developed and tested in Laghos, to the large-scale multi-physics settings of the MARBL code. The low-level CEED API provides a set of FE kernels and components for writing new low-level kernels. Examples include: vector and sparse linear algebra, element matrix assembly over a batch of elements, partial assembly and action for efficient high-order operators like mass, diffusion, advection, etc. The main goal of the low-level API is to establish the basis for the high-level API. Also, identifying such low-level kernels and providing a reference implementation for them serves as the basis for collaboration with vendors and STs. Another goal for the low-level API is to make it easy for applications with their own discretization infrastructure, who do not want to switch directly to using the high-level CEED API, to still evaluate and use the core operations provided by the low-level API. One of the challenges with high-order methods is that a global sparse matrix is no longer a good representation of a high-order linear operator, both with respect to the FLOPs needed for its evaluation, as well as the memory transfer needed for a matvec. Thus, another important question we tried to address while developing the low-level API is: is it possible to abstract out in a natural and efficient way the different implementations and data structures that arise when dealing with various computational device types: CPUs, GPUs, etc. Fully answering this question is beyond the scope of this particular milestone, since that requires longer time as we develop and expand the devices we support. The future high-level API will be the frontend provided by CEED consisting of high-level abstractions such as meshes, finite element spaces and solutions, bilinear forms, solvers, etc. At this high-level, an important aspect of the API will be to provide a uniform abstraction layer for writing code in a portable manner. To achieve that, we plan to utilize the MPI programming model combined with a device abstraction layer (DAL) for finite element computations that we will develop. The DAL will serve as the bridge between the low- and the high-level APIs, allowing a variety of programming models to be used for the low-level kernel implementations. The software artifacts delivered as part of this milestone include an initial CEED API software implementation (libCEED) provided through the CEED website, http://ceed.exascaleproject.org and the CEED GitHub organization, http://github.com/ceed. In addition to details and results from the above R&D efforts, in this document we are also reporting on other project-wide activities performed in Q1 of FY18, including: the Nek5000 v17.0 MFEM v3.3.2 and PETSc v3.8 releases, collaborations with ECP/ST and SciDAC projects, the inaugural Nek5000 hackathon and various outreach activities.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

A matrix-free approach for finite-strain hyperelastic problems using geometric multigrid

This paper investigates matrix-free algorithms for problems in quasi-static finite-strain hyperelasticity. Iterative solvers with matrix-free operator evaluation have emerged as an attractive alternative to sparse matrices in the fluid dynamics and wave propagation communities because they significantly reduce the memory traffic, the limiting factor in classical finite element solvers. Specifically, we study different matrix-free realizations of the finite element tangent operator and determine whether generalized methods of incorporating complex constitutive behavior might be feasible. Furthermore, in order to improve the convergence behavior of iterative solvers, we also propose a method by which to construct level tangent operators and employ them to define a geometric multigrid preconditioner. Additionally, the performance of the matrix-free operator and the geometric multigrid preconditioner is compared to the matrix-based implementation with an algebraic multigrid (AMG) preconditioner on a single node for a representative numerical example of a heterogeneous hyperelastic material in two and three dimensions. We find that matrix-free methods for finite-strain solid mechanics are very promising, outperforming linear matrix-based schemes by two to five times, and that it is possible to develop numerically efficient implementations that are independent of the hyperelastic constitutive law.

42 ENGINEERING↗