MINRES-QLP: a Krylov subspace method for indefinite or singular symmetric systems

Abstract

CG, SYMMLQ, and MINRES are Krylov subspace methods for solving symmetric systems of linear equations. When these methods are applied to an incompatible system (that is, a singular symmetric least-squares problem), CG could break down and SYMMLQ's solution could explode, while MINRES would give a least-squares solution but not necessarily the minimum-length (pseudoinverse) solution. This understanding motivates us to design a MINRES-like algorithm to compute minimum-length solutions to singular symmetric systems. MINRES uses QR factors of the tridiagonal matrix from the Lanczos process (where R is upper-tridiagonal). MINRES-QLP uses a QLP decomposition (where rotations on the right reduce R to lower-tridiagonal form). On ill-conditioned systems (singular or not), MINRES-QLP can give more accurate solutions than MINRES. We derive preconditioned MINRES-QLP, new stopping rules, and better estimates of the solution and residual norms, the matrix norm, and the condition number.

26 pages, 6 figures

References in corpus (1)

• ALGORITHM 937: MINRES-QLP for Singular Symmetric and Hermitian Linear Equations and Least-Squares Problems

Cited by in corpus (26)

• Variational Quantum Monte Carlo Method with a Neural-Network Ansatz for Open Quantum Systems
• Multi-reference many-body perturbation theory for nuclei III -- Ab initio calculations at second order in PGCM-PT
• Imposing Hard Constraints on Deep Networks: Promises and Limitations
• ALGORITHM 937: MINRES-QLP for Singular Symmetric and Hermitian Linear Equations and Least-Squares Problems
• Hodge Laplacians on graphs
• Laser pulse driven control of charge and spin order in the two-dimensional Kondo lattice
• Wave function methods for canonical ensemble thermal averages in correlated many-fermion systems
• Strategies and performance of the CMS silicon tracker alignment during LHC Run 2
• Confirming the role of nuclear tunnelling in aqueous ferrous-ferric electron transfer
• Convergence of Newton-MR under Inexact Hessian Information
• An incompressible Eulerian method for fluid-structure interaction with mixed soft and rigid solids
• Solver for the electronic V-representation problem of time-dependent density functional theory
• Minimal Residual Methods for Complex Symmetric, Skew Symmetric, and Skew Hermitian Systems
• LSMR: An iterative algorithm for sparse least-squares problems
• TriCG and TriMR: Two Iterative Methods for Symmetric Quasi-Definite Systems
• Natural Gradient Deep Q-learning
• Nodal auxiliary space preconditioning for the surface de Rham complex
• Inexact Sequential Quadratic Optimization for Minimizing a Stochastic Objective Function Subject to Deterministic Nonlinear Equality Constraints
• Preconditioned steepest descent-like methods for symmetric indefinite systems
• Absorption kinetics of vacancies by cavities in Aluminum: numerical characterization of sink strengths and first-passage statistics through Krylov subspace projection and eigenvalue deflation
• Analysis of the inference of ratings and rankings in complex networks using discrete exterior calculus on higher--order networks
• Approximate Generalized Inverses with Iterative Refinement for $\epsilon$-Accurate Preconditioning of Singular Systems
• A Nonmonotone Matrix-Free Algorithm for Nonlinear Equality-Constrained Least-Squares Problems
• OPINS: An Orthogonally Projected Implicit Null-space Method for Singular and Nonsingular Saddle-point Systems
• Non-PSD Matrix Sketching with Applications to Regression and Optimization
• An active-set algorithm for norm constrained quadratic problems