MINRES-QLP: A Krylov Subspace Method for Indefinite or Singular Symmetric Systems

By Sou-Cheng T. Choi, C. Paige, Michael A. Saunders. 2010

128 citations recorded by the source corpus.

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.

Subfields: Atomic and Molecular Physics, and Optics, Computational Theory and Mathematics, Numerical Analysis, Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Atomic and Molecular Physics, and Optics

In Computational Theory and Mathematics

In Numerical Analysis

In Numerical Methods & Scientific Computing

Citations in the corpus

Revisiting Natural Gradient for Deep Networks (2013, methodology): “In order to better deal with singular and ill-conditioned matrices we use the MinRes-QLP algorithm (Choi et al. , 2011) instead of linear conjugate gradient for certain experiments.”
DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization (2019, methodology): “For DINGO, we use the sub-problem solvers MINRES-QLP [22], LSMR [23] and CG [24] when computing Ht,igt, H̃ † t,ig̃t and (H̃ T t,iH̃t,i) (Htgt), respectively.”
Natural Gradient Deep Q-learning (2018, methodology): “The MinRes-QLP Algorithm solves this linear equation by extending MinRes, an existing Krylov subspace descent algorithm to solve linear equations, to ill-conditioned systems such as a singular FIM using the QLP decomposition of the tridiagonal matrix from the Lanczos process [Choi et al., 2011].”
Imposing Hard Constraints on Deep Networks: Promises and Limitations (2017, methodology): “The Krylov subspace approach we introduced in Section 4.3 has made those computationally tractable despite the enormous size of the linear systems while the MINRES-QLP approach [3] to solving them delivers numerical stability even though the matrices are ill-conditioned.”