Search NASA⌕ Search

SEARCH · Search NASA

Results for “Krylov subspace methods”

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
NASA NTRS1989

Overview of Krylov subspace methods with applications to control problems

An overview of projection methods based on Krylov subspaces are given with emphasis on their application to solving matrix equations that arise in control problems. The main idea of Krylov subspace methods is to generate a basis of the Krylov subspace Span and seek an approximate solution the the original problem from this subspace. Thus, the original matrix problem of size N is approximated by one of dimension m typically much smaller than N. Krylov subspace methods have been very successful in solving linear systems and eigenvalue problems and are now just becoming popular for solving nonlinear equations. It is shown how they can be used to solve partial pole placement problems, Sylvester's equation, and Lyapunov's equation.

Saad, Youcef↗
NASA NTRS1990

Krylov subspace methods - Theory, algorithms, and applications

Projection methods based on Krylov subspaces for solving various types of scientific problems are reviewed. The main idea of this class of methods when applied to a linear system Ax = b, is to generate in some manner an approximate solution to the original problem from the so-called Krylov subspace span. Thus, the original problem of size N is approximated by one of dimension m, typically much smaller than N. Krylov subspace methods have been very successful in solving linear systems and eigenvalue problems and are now becoming popular for solving nonlinear equations. The main ideas in Krylov subspace methods are shown and their use in solving linear systems, eigenvalue problems, parabolic partial differential equations, Liapunov matrix equations, and nonlinear system of equations are discussed.

Sad, Youcef↗
NASA NTRS1992

Application of vector-valued rational approximations to the matrix eigenvalue problem and connections with Krylov subspace methods

Let F(z) be a vectored-valued function F: C approaches C sup N, which is analytic at z=0 and meromorphic in a neighborhood of z=0, and let its Maclaurin series be given. We use vector-valued rational approximation procedures for F(z) that are based on its Maclaurin series in conjunction with power iterations to develop bona fide generalizations of the power method for an arbitrary N X N matrix that may be diagonalizable or not. These generalizations can be used to obtain simultaneously several of the largest distinct eigenvalues and the corresponding invariant subspaces, and present a detailed convergence theory for them. In addition, it is shown that the generalized power methods of this work are equivalent to some Krylov subspace methods, among them the methods of Arnoldi and Lanczos. Thus, the theory provides a set of completely new results and constructions for these Krylov subspace methods. This theory suggests at the same time a new mode of usage for these Krylov subspace methods that were observed to possess computational advantages over their common mode of usage.

Sidi, Avram↗
NASA NTRS1996

Multigrid and Krylov Subspace Methods for Transport Equations: Absorption Case

In this paper we look at Krylov subspace methods for solving the transport equations in a slab geometry. The spatial discretization scheme used is a finite element method called Modified Linear Discontinuous scheme (MLD). We investigate the convergence rates for a number of Krylov subspace methods for this problem and compare with the results of a spatial multigrid scheme.

Oliveira, S.↗
NASA NTRS1991

Krylov Subspace Methods for Complex Non-Hermitian Linear Systems

We consider Krylov subspace methods for the solution of large sparse linear systems Ax = b with complex non-Hermitian coefficient matrices. Such linear systems arise in important applications, such as inverse scattering, numerical solution of time-dependent Schrodinger equations, underwater acoustics, eddy current computations, numerical computations in quantum chromodynamics, and numerical conformal mapping. Typically, the resulting coefficient matrices A exhibit special structures, such as complex symmetry, or they are shifted Hermitian matrices. In this paper, we first describe a Krylov subspace approach with iterates defined by a quasi-minimal residual property, the QMR method, for solving general complex non-Hermitian linear systems. Then, we study special Krylov subspace methods designed for the two families of complex symmetric respectively shifted Hermitian linear systems. We also include some results concerning the obvious approach to general complex linear systems by solving equivalent real linear systems for the real and imaginary parts of x. Finally, numerical experiments for linear systems arising from the complex Helmholtz equation are reported.

Freund, Roland W.↗
DOE OSTI2025

Krylov Subspace Methods for Quantum Dynamics with Time-Dependent Generators

Krylov subspace methods in quantum dynamics identify the minimal subspace in which a process unfolds. To date, their use is restricted to time evolutions governed by time-independent generators. Here, we introduce a generalization valid for driven quantum systems governed by a time-dependent Hamiltonian that maps the evolution to a diffusion problem in a one-dimensional lattice with nearest-neighbor hopping probabilities that are inhomogeneous and time dependent. This representation is used to establish a novel class of fundamental limits to the quantum speed of evolution and operator growth. We also discuss generalizations of the algorithm, adapted to discretized time evolutions and periodic Hamiltonians, with applications to many-body systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1988

Krylov subspace methods on supercomputers

A short survey of recent research on Krylov subspace methods with emphasis on implementation on vector and parallel computers is presented. Conjugate gradient methods have proven very useful on traditional scalar computers, and their popularity is likely to increase as three-dimensional models gain importance. A conservative approach to derive effective iterative techniques for supercomputers has been to find efficient parallel/vector implementations of the standard algorithms. The main source of difficulty in the incomplete factorization preconditionings is in the solution of the triangular systems at each step. A few approaches consisting of implementing efficient forward and backward triangular solutions are described in detail. Polynomial preconditioning as an alternative to standard incomplete factorization techniques is also discussed. Another efficient approach is to reorder the equations so as to improve the structure of the matrix to achieve better parallelism or vectorization. An overview of these and other ideas and their effectiveness or potential for different types of architectures is given.

Saad, Youcef↗
DOE OSTI2022

A Comparison of Linear Solvers for Resolving Flow in Three-Dimensional Discrete Fracture Networks

We compare various methods for resolving steady flow within three-dimensional discrete fracture networks, including direct methods, Krylov subspace methods with and without preconditioning, and multi-grid methods. We compared the performance of the methods based on compute times and scaling of the solution as a function of the number of grid nodes and log-variance of the hydraulic aperture. The methods are applied to three test cases: (a) variable density of networks with a truncated power-law distribution of fracture lengths, (b) a fixed network composed of monodisperse fracture sizes but varied permeability/aperture heterogeneity, (c) and a network based on field site in Nevada, US. We chose these cases to allow us to study the impact of the mesh size and flow properties, as well as to demonstrate our conclusions on a large-scale, realistic problem (more than 40 million mesh nodes). A direct solution using Cholesky factorization outperformed other methods for every example but was closely followed in performance by some algebraic multigrid (AMG) preconditioned Krylov subspace methods. Among the Krylov methods, conjugate gradients (CG) with an AMG preconditioner performs the best. Generally, Cholesky factorization is recommended, but CG with an AMG preconditioner may be suitable for very large problems beyond 40 million nodes where the entire linear system cannot reside in memory.

58 GEOSCIENCES↗
NASA NTRS1996

Multigrid and Krylov Subspace Methods for the Discrete Stokes Equations

Discretization of the Stokes equations produces a symmetric indefinite system of linear equations. For stable discretizations, a variety of numerical methods have been proposed that have rates of convergence independent of the mesh size used in the discretization. In this paper, we compare the performance of four such methods: variants of the Uzawa, preconditioned conjugate gradient, preconditioned conjugate residual, and multigrid methods, for solving several two-dimensional model problems. The results indicate that where it is applicable, multigrid with smoothing based on incomplete factorization is more efficient than the other methods, but typically by no more than a factor of two. The conjugate residual method has the advantage of being both independent of iteration parameters and widely applicable.

Elman, Howard C.↗
NASA NTRS1996

Preserving Symmetry in Preconditioned Krylov Subspace Methods

We consider the problem of solving a linear system Ax = b when A is nearly symmetric and when the system is preconditioned by a symmetric positive definite matrix M. In the symmetric case, one can recover symmetry by using M-inner products in the conjugate gradient (CG) algorithm. This idea can also be used in the nonsymmetric case, and near symmetry can be preserved similarly. Like CG, the new algorithms are mathematically equivalent to split preconditioning, but do not require M to be factored. Better robustness in a specific sense can also be observed. When combined with truncated versions of iterative methods, tests show that this is more effective than the common practice of forfeiting near-symmetry altogether.

Chan, Tony F.↗
NASA NTRS1996

Practical Aspects of Krylov Subspace Iterative Methods in CFD

Implementation issues associated with the application of Krylov subspace iterative methods, such as Newton-GMRES, are presented within the framework of practical computational fluid dynamic (CFD) applications. This paper categorizes, evaluates, and contrasts the major ingredients (function evaluations, matrix-vector products, and preconditioners) of Newton-GMRES Krylov subspace methods in terms of their effect on the local linear and global nonlinear convergence, memory requirements, and accuracy. The discussion focuses on Newton-GMRES in both a structured multi-zone incompressible Navier-Stokes solver and an unstructured mesh finite-volume Navier-Stokes solver. Approximate versus exact matrix-vector products, effective preconditioners, and other pertinent issues are addressed.

Pulliam, Thomas H.↗
NASA NTRS1991

Distributed Minimal Residual (DMR) method for acceleration of iterative algorithms

A new method for enhancing the convergence rate of iterative algorithms for the numerical integration of systems of partial differential equations was developed. It is termed the Distributed Minimal Residual (DMR) method and it is based on general Krylov subspace methods. The DMR method differs from the Krylov subspace methods by the fact that the iterative acceleration factors are different from equation to equation in the system. At the same time, the DMR method can be viewed as an incomplete Newton iteration method. The DMR method was applied to Euler equations of gas dynamics and incompressible Navier-Stokes equations. All numerical test cases were obtained using either explicit four stage Runge-Kutta or Euler implicit time integration. The formulation for the DMR method is general in nature and can be applied to explicit and implicit iterative algorithms for arbitrary systems of partial differential equations.

Lee, Seungsoo↗
NASA NTRS2000

Ordering Unstructured Meshes for Sparse Matrix Computations on Leading Parallel Systems

The ability of computers to solve hitherto intractable problems and simulate complex processes using mathematical models makes them an indispensable part of modern science and engineering. Computer simulations of large-scale realistic applications usually require solving a set of non-linear partial differential equations (PDES) over a finite region. For example, one thrust area in the DOE Grand Challenge projects is to design future accelerators such as the SpaHation Neutron Source (SNS). Our colleagues at SLAC need to model complex RFQ cavities with large aspect ratios. Unstructured grids are currently used to resolve the small features in a large computational domain; dynamic mesh adaptation will be added in the future for additional efficiency. The PDEs for electromagnetics are discretized by the FEM method, which leads to a generalized eigenvalue problem Kx = AMx, where K and M are the stiffness and mass matrices, and are very sparse. In a typical cavity model, the number of degrees of freedom is about one million. For such large eigenproblems, direct solution techniques quickly reach the memory limits. Instead, the most widely-used methods are Krylov subspace methods, such as Lanczos or Jacobi-Davidson. In all the Krylov-based algorithms, sparse matrix-vector multiplication (SPMV) must be performed repeatedly. Therefore, the efficiency of SPMV usually determines the eigensolver speed. SPMV is also one of the most heavily used kernels in large-scale numerical simulations.

Oliker, Leonid↗
NASA NTRS1989

Globally convergent techniques in nonlinear Newton-Krylov

Some convergence theory is presented for nonlinear Krylov subspace methods. The basic idea of these methods is to use variants of Newton's iteration in conjunction with a Krylov subspace method for solving the Jacobian linear systems. These methods are variants of inexact Newton methods where the approximate Newton direction is taken from a subspace of small dimensions. The main focus is to analyze these methods when they are combined with global strategies such as linesearch techniques and model trust region algorithms. Most of the convergence results are formulated for projection onto general subspaces rather than just Krylov subspaces.

Brown, Peter N.↗
DOE OSTI2025

Towards a Quantum Algorithm for the Incompressible Nonlinear Navier-Stokes Equations

In this work, we present novel concepts for quantum algorithms to solve transient, nonlinear partial differential equations (PDEs). The challenge lies in how to effectively represent, encode, process, and evolve the nonlinear system of PDEs on quantum computers. We will discuss the new techniques using the incompressible Navier-Stokes equations as an example, because it represents the fundamental nonlinear feature and yet removes certain complexity in physics, allowing us to focus on the design of quantum algorithms. Previous attempts solving nonlinear PDEs in quantum computation have often involved storing multiple copies of solutions or employing linearizations. Neither is practical due to exponential scaling with evolution time or insufficient solution accuracy. We propose a new framework based on matrix product states (MPSs) and matrix product operators (MPOs), in addition to the Krylov subspace methods. For example, the solution variables of the Navier-Stokes equations are represented by MPSs, and the linear and nonlinear terms are processed by MPOs. The time evolution of the operators is attained by a fast-forwarding algorithm using Krylov subspace methods. Furthermore, we discuss various techniques for efficient encoding of MPSs, measurement reduction for MPOs, and use of tensor operations to treat multi-variate, multi-physics characteristics of Navier-Stokes.

Gopalakrishnan Meena, Murali [ORNL] (ORCID:0000000↗
NASA NTRS1989

Projection methods for the numerical solution of Markov chain models

Projection methods for computing stationary probability distributions for Markov chain models are presented. A general projection method is a method which seeks an approximation from a subspace of small dimension to the original problem. Thus, the original matrix problem of size N is approximated by one of dimension m, typically much smaller than N. A particularly successful class of methods based on this principle is that of Krylov subspace methods which utilize subspaces of the form span(v,av,...,A(exp m-1)v). These methods are effective in solving linear systems and eigenvalue problems (Lanczos, Arnoldi,...) as well as nonlinear equations. They can be combined with more traditional iterative methods such as successive overrelaxation, symmetric successive overrelaxation, or with incomplete factorization methods to enhance convergence.

Saad, Youcef↗
NASA NTRS1994

Preconditioned conjugate gradient methods for the Navier-Stokes equations

A preconditioned Krylov subspace method (GMRES) is used to solve the linear systems of equations formed at each time-integration step of the unsteady, two-dimensional, compressible Navier-Stokes equations of fluid flow. The Navier-Stokes equations are cast in an implicit, upwind finite-volume, flux-split formulation. Several preconditioning techniques are investigated to enhance the efficiency and convergence rate of the implicit solver based on the GMRES algorithm. The superiority of the new solver is established by comparisons with a conventional implicit solver, namely line Gauss-Seidel relaxation (LGSR). Computational test results for low-speed (incompressible flow over a backward-facing step at Mach 0.1), transonic flow (trailing edge flow in a transonic turbine cascade), and hypersonic flow (shock-on-shock interactions on a cylindrical leading edge at Mach 6.0) are presented. For the Mach 0.1 case, overall speedup factors of up to 17 (in terms of time-steps) and 15 (in terms of CPU time on a CRAY-YMP/8) are found in favor of the preconditioned GMRES solver, when compared with the LGSR solver. The corresponding speedup factors for the transonic flow case are 17 and 23, respectively. The hypersonic flow case shows slightly lower speedup factors of 9 and 13, respectively. The study of preconditioners conducted in this research reveals that a new LUSGS-type preconditioner is much more efficient than a conventional incomplete LU-type preconditioner.

Ajmani, Kumud↗