Optimization Online


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

Sou-Cheng Choi (scchoi***at***stanford.edu)
Christopher Paige (paige***at***cs.mcgill.ca)
Michael Saunders (saunders***at***stanford.edu)

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.

Keywords: MINRES, Krylov subspace method, Lanczos process, conjugate-gradient method, minimum-residual method, ill-posed problem, singular least-squares problem, sparse matrix

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- Science and Engineering (Statistics )

Category 3: Optimization Software and Modeling Systems

Citation: Systems Optimization Laboratory (SOL), Stanford University, March 2010

Download: [PDF]

Entry Submitted: 03/16/2010
Entry Accepted: 03/16/2010
Entry Last Modified: 04/03/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society