Search NASA⌕ Search

SEARCH · Search NASA

Results for “krylov solvers”

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 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Two-Stage Gauss-Seidel Preconditioners and Smoothers for Krylov Solvers on a GPU Cluster: Preprint

Gauss-Seidel (GS) relaxation is often employed as a preconditioner for a Krylov solver or as a smoother for Algebraic Multigrid (AMG). However, the requisite sparse triangular solve is difficult to parallelize on many-core architectures such as graphics processing units (GPUs). In the present study, the performance of the sequential GS relaxation based on a triangular solve is compared with two-stage variants, replacing the direct triangular solve with a fixed number of inner Jacobi-Richardson (JR) iterations. When a small number of inner iterations is sufficient to maintain the Krylov convergence rate, the two-stage GS (GS2) often outperforms the sequential algorithm on many-core architectures. The GS2 algorithm is also compared with JR. When they perform the same number of ops for SpMV (e.g. three JR sweeps compared to two GS sweeps with one inner JR sweep), the GS2 iterations, and the Krylov solver preconditioned with GS2, may converge faster than the JR iterations. Moreover, for some problems (e.g. elasticity), it was found that JR may diverge with a damping factor of one, whereas two-stage GS may improve the convergence with more inner iterations. Finally, to study the performance of the two-stage smoother and preconditioner for a practical problem, these were applied to incompressible uid ow simulations on GPUs.

algebraic multigrid↗
DOE OSTI2020

Understanding performance variability in standard and pipelined parallel Krylov solvers

In this work, we collect data from runs of Krylov subspace methods and pipelined Krylov algorithms in an effort to understand and model the impact of machine noise and other sources of variability on performance. We find large variability of Krylov iterations between compute nodes for standard methods that is reduced in pipelined algorithms, directly supporting conjecture, as well as large variation between statistical distributions of runtimes across iterations. Based on these results, we improve upon a previously introduced nondeterministic performance model by allowing iterations to fluctuate over time. We present our data from runs of various Krylov algorithms across multiple platforms as well as our updated non-stationary model that provides good agreement with observations. We also suggest how it can be used as a predictive tool.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Low-synch Gram–Schmidt with delayed reorthogonalization for Krylov solvers

The parallel strong-scaling of iterative methods is often determined by the number of global reductions at each iteration. Low-synch Gram-Schmidt algorithms are applied here to the Arnoldi algorithm to reduce the number of global reductions and therefore to improve the parallel strong-scaling of iterative solvers for nonsymmetric matrices such as the GMRES and the Krylov-Schur iterative methods. In the Arnoldi context, the factorization is "left-looking" and processes one column at a time. Among the methods for generating an orthogonal basis for the Arnoldi algorithm, the classical Gram-Schmidt algorithm, with reorthogonalization (CGS2) requires three global reductions per iteration. A new variant of CGS2 that requires only one reduction per iteration is presented and applied to the Arnoldi algorithm. Delayed CGS2 (DCGS2) employs the minimum number of global reductions per iteration (one) for a one-column at-a-time algorithm. The main idea behind the new algorithm is to group global reductions by rearranging the order of operations. DCGS2 must be carefully integrated into an Arnoldi expansion or a GMRES solver. Numerical stability experiments assess robustness for Krylov-Schur eigenvalue computations. Performance experiments on the ORNL Summit supercomputer then establish the superiority of DCGS2 over CGS2.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1994

Discrete sensitivity derivatives of the Navier-Stokes equations with a parallel Krylov solver

This paper solves an 'incremental' form of the sensitivity equations derived by differentiating the discretized thin-layer Navier Stokes equations with respect to certain design variables of interest. The equations are solved with a parallel, preconditioned Generalized Minimal RESidual (GMRES) solver on a distributed-memory architecture. The 'serial' sensitivity analysis code is parallelized by using the Single Program Multiple Data (SPMD) programming model, domain decomposition techniques, and message-passing tools. Sensitivity derivatives are computed for low and high Reynolds number flows over a NACA 1406 airfoil on a 32-processor Intel Hypercube, and found to be identical to those computed on a single-processor Cray Y-MP. It is estimated that the parallel sensitivity analysis code has to be run on 40-50 processors of the Intel Hypercube in order to match the single-processor processing time of a Cray Y-MP.

Ajmani, Kumud↗
NASA NTRSDate not supplied

Numerical Behaviour of a Smooth Local Correlation-based Transition Model in a Newton-Krylov Flow Solver

The numerical behaviour of transport-equation-based transition models, including both iterative and grid convergence, is influenced by the source terms. Transition models contain source terms that are large and highly nonlinear, and can be destabilizing in a strong implicit solver. Linearization strategies with varying levels of coupling are evaluated in conjunction with a source-term time step restriction to determine best-practices for solving the SA-sLM2015smooth local correlation-based transition model in an implicit Newton-Krylov flow solver. Achieving deep iterative convergence facilitates a detailed investigation of the grid convergence of these free-transition simulations, which are evaluated relative to fully-turbulent simulations performed using the Spalart-Allmaras turbulence model. Simulations of the NLF0416 general aviation airfoil, VA-2 supercritical airfoil, and NASA CRM-NLF wing-body geometry are performed over a range of grid levels. The results demonstrate that both a fully-coupled linearization strategy and a source-term time step restriction improve nonlinear convergence as the complexity of the free-transition simulations increases. In general, additional grid resolution is required for free-transition simulations relative to fully-turbulent simulations in order to achieve a similar level of accuracy, with the grid convergence of free-transition simulations sensitive to the streamwise grid spacings in the transition regions.

AATT↗
DOE OSTI2021

Benchmarking Quantum Chemistry Computations with Variational, Imaginary Time Evolution, and Krylov Space Solver Algorithms

Quantum chemistry is a key application area for noisy-intermediate scale quantum (NISQ) devices, and therefore serves as an important benchmark for current and future quantum computer performance. Previous benchmarks in this field have focused on variational methods for computing ground and excited states of various molecules, including a benchmarking suite focused on the performance of computing ground states for alkali-hydrides under an array of error mitigation methods. State-of-the-art methods to reach chemical accuracy in hybrid quantum-classical electronic structure calculations of alkali hydride molecules on NISQ devices from IBM are outlined here. Here it is demonstrated how to extend the reach of variational eigensolvers with symmetry preserving Ansätze. Next, it is outlined how to use quantum imaginary time evolution and Lanczos as a complementary method to variational techniques, highlighting the advantages of each approach. Finally, a new error mitigation method is demonstrated which uses systematic error cancellation via hidden inverse gate constructions, improving the performance of typical variational algorithms. These results show that electronic structure calculations have advanced rapidly, to routine chemical accuracy for simple molecules, from their inception on quantum computers a few short years ago, and they point to further rapid progress to larger molecules as the power of NISQ devices grows.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Neumann Series in MGS-GMRES and Inner-Outer Iterations: Preprint

A low-synchronization MGS-GMRES Krylov solver employing a truncated Neumann series for the inverse compact WY MGS correction matrix T is presented. A corollary to the backward stability result of Paige et al. [1] establishes that T = I - Lk is sufficient for convergence of GMRES when kLkp F = O("p)_p F (B), where the strictly lower triangular matrix L is defined by the inner products of Krylov vectors V T 1:k-2 vk-1. The preconditioner is the classical Ruge-Stuben AMG algorithm with compatible relaxation and inner-outer Gauss-Seidel smoother. This smoother may also be expressed as a truncated Neumann series. Drop tolerances are applied to the lower triangular matrices arising in the smoother in order to reduce the number of non-zeros and accelerate the time to solution. The number of small matrix elements are found to increase from fine to coarse levels and thus the effciency gains are greater for large problems with many levels in the V -cycle. The solver is applied to the pressure continuity equation for the incompressible Navier-Stokes equations. Unlike the inner-outer iteration, the solver convergence rate with the standard Gauss-Seidel smoother deteriorates with dropping. The solver compute time is reduced by up to 50% without a change in the convergence rate.

Gauss-Seidel smoother↗
DOE OSTI2026

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↗
NASA NTRSDate not supplied

Efficient Preconditioning of a High-Order Solver for Multiple Physics

This work addresses preconditioning approaches for an implicit high-order solver frame-work applied to multiple physics. The solver is based on a space-time spectral element method and matrix-free Newton-Krylov solver developed at NASA over the recent years. Within this context, most preconditioning methods are impractical, as the computational time and memory requirements scale poorly with increasing polynomial orders. To improve computational efficiency, we first describe a novel entity-based Block Jacobi preconditioner for the continuous-Galerkin solution of the linear-elasticity and linear-shell equations. Second, we introduce a multigrid algorithm to further reduce time-to-solution on stiff cases arising from continuous-and discontinuous-Galerkin discretizations. Results obtained on relevant single-physics reference solutions, demonstrate the feasibility of the methods, paving the way for high-order solutions of fully coupled multi-physics problems.

STMD↗
DOE OSTI2026

Speedup of UEDGE Parameter Scans Using Machine-Learning Optimized OpenMP Parallelization and a Continuation Solver

This article presents the OpenMP parallelization of the preconditioning Jacobian assembly and right‐hand side residual evaluation in UEDGE. A continuation algorithm, utilizing the internal NKSOL implicit Jacobian‐Free Newton‐Krylov solver to efficiently scan physical parameters, is also presented. The implemented parallelization reduces the computational time for a benchmark scan run on 32 threads by compared to the serial version when using trained random forest regression models to identify the optimal decomposition of the system of equations. Random forest regression models applied to the UEDGE time‐dependent and continuation solver algorithms did not yield meaningful improvement in computational performance. A benchmark DIII‐D gas injection rate scan in the 0.35–0.75 kA interval, performed on a test cluster using the parallelized code and continuation solver, produced 1066 steady‐state solutions with a 22 s average wall‐clock computational time per steady‐state solution.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2025

Randomized Algorithms for Linear Solvers

Recently, randomized algorithms in numerical linear algebra, specifically those centered around random sketching, have gained traction in primarily theoretical research due to their potential to significantly reduce problem dimensionality at the cost of an O(1) multiplicative distortion factor. It has been assumed that this sketching can be done efficiently, but thorough investigation into how precisely to do it has been neglected. Moreover, the theory-based community has argued for sketching’s ability to reduce computational cost via complexity analysis, but has not researched how it affects the stability of the algorithms. At Sandia, efficient linear solvers that scale well on modern HPC architectures while maintaining stability are imperative for practical applications. In this LDRD, we developed a random sketching strategy that is substantially faster than existing ones, and demonstrate its superior performance in practice on a NVIDIA H100 GPU. Moreover, we show how this can be used to significantly outperform existing linear least squares solvers while improving the solver’s stability as well. Additionally, we demonstrate how this sketching strategy can be used to make a fast, stable QR factorization that can subsequently be used in s-step and block Krylov solvers. Finally, we incorporate a sketching-based block orthogonalization scheme into s-step GMRES, which is stable and faster than existing approaches on the Perlmutter supercomputer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Fast GPU 3D diffeomorphic image registration

3D image registration is one of the most fundamental and computationally expensive operations in medical image analysis. Here, we present a mixed-precision, Gauss–Newton–Krylov solver for diffeomorphic registration of two images. Our work extends the publicly available CLAIRE library to GPU architectures. Despite the importance of image registration, only a few implementations of large deformation diffeomorphic registration packages support GPUs. Our contributions are new algorithms to significantly reduce the run time of the two main computational kernels in CLAIRE: calculation of derivatives and scattered-data interpolation. Additionally, we deploy (i) highly-optimized, mixed-precision GPU-kernels for the evaluation of scattered-data interpolation, (ii) replace Fast-Fourier-Transform (FFT)-based first-order derivatives with optimized 8th-order finite differences, and (iii) compare with state-of-the-art CPU and GPU implementations. As a highlight, we demonstrate that we can register clinical images in less than 6 s on a single NVIDIA Tesla V100. This amounts to over 20 speed-up over the current version of CLAIRE and over 30 speed-up over existing GPU implementations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Preconditioners for multiphase poromechanics with strong capillarity

This paper aims to enhance the performance of Newton–Krylov solvers for coupled poromechanical problems with two-phase flow. In particular, we investigate the impact of capillary pressure on preconditioning strategies. Capillarity complicates the coupling between the solid deformation and fluid pressure degrees of freedom, as well as increases the nonlinearity of the system. Depending on the capillary pressure relation used in the constitutive formulation, the flow equations may exhibit a spectrum of advection-dominated to diffusion-dominated behavior. We propose preconditioning approaches that account for this behavior and lead to robust numerical performance within a broad range of regimes.

42 ENGINEERING↗
DOE OSTI2021

Toward efficient polynomial preconditioning for GMRES

Here, we present a polynomial preconditioner for solving large systems of linear equations. The polynomial is derived from the minimum residual polynomial (the GMRES polynomial) and is more straightforward to compute and implement than many previous polynomial preconditioners. Our current implementation of this polynomial using its roots is naturally more stable than previous methods of computing the same polynomial. We implement further stability control using added roots, and this allows for high degree polynomials. We discuss the effectiveness and challenges of root-adding and give an additional check for stability. In this article, we study the polynomial preconditioner applied to GMRES; however it could be used with any Krylov solver. This polynomial preconditioning algorithm can dramatically improve convergence for some problems, especially for difficult problems, and can reduce dot products by an even greater margin.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2009

Three-dimensional Finite Element Formulation and Scalable Domain Decomposition for High Fidelity Rotor Dynamic Analysis

This paper has two objectives. The first objective is to formulate a 3-dimensional Finite Element Model for the dynamic analysis of helicopter rotor blades. The second objective is to implement and analyze a dual-primal iterative substructuring based Krylov solver, that is parallel and scalable, for the solution of the 3-D FEM analysis. The numerical and parallel scalability of the solver is studied using two prototype problems - one for ideal hover (symmetric) and one for a transient forward flight (non-symmetric) - both carried out on up to 48 processors. In both hover and forward flight conditions, a perfect linear speed-up is observed, for a given problem size, up to the point of substructure optimality. Substructure optimality and the linear parallel speed-up range are both shown to depend on the problem size as well as on the selection of the coarse problem. With a larger problem size, linear speed-up is restored up to the new substructure optimality. The solver also scales with problem size - even though this conclusion is premature given the small prototype grids considered in this study.

Datta, Anubhav↗