SOL Logo

Systems Optimization Laboratory

Stanford University
Dept of Management Science and Engineering (MS&E)

Huang Engineering Center

Stanford, CA 94305-4121  USA

MINRES-QLP: Sparse Symmetric Equations or Least-Squares Problems

  • AUTHORS: S.-C. T. Choi, M. A. Saunders.
  • CONTRIBUTORS: C. C. Paige.
  • CONTENTS: Implementation of a conjugate-gradient type method for solving sparse linear equations: \begin{align*} \text{Solve } & Ax=b \\ \text{or } & (A - sI)x = b \\ \text{or minimize } & \|Ax-b\|^2 \\ \text{or minimize } & \|(A - sI)x-b\|^2 \end{align*} The matrix \(A - sI\) must be symmetric or Hermitian, but it may be definite or indefinite, singular or nonsingular. The scalar \(s\) is a shifting parameter – it may be any real number. The method is based on Lanczos tridiagonalization. You may provide a preconditioner, but it must be symmetric positive definite.

    If \((A - sI)\) is nonsingular, use SYMMLQ or MINRES.

    If \((A - sI)x = b\) is singular and compatible, use MINRES or MINRES-QLP (this routine).

    If \((A - sI)x = b\) is singular and incompatible, use MINRES-QLP (this routine).

    If \(A\) is unsymmetric or rectangular, use LSQR or LSMR.

    Special application: To find a null vector of a singular symmetric or Hermitian matrix \(A\), apply MINRES-QLP to the system \( \min \|Ax - b\| \) with any nonzero vector \(b\) (e.g. a random \(b\)). At a minimizer, the residual vector \(r = b - Ax \) will satisfy \( Ar=0 \). See [1] for examples.

    If an eigenvalue \( \lambda \) is known, the associated eigenvector may be obtained by applying MINRES-QLP to \((A - \lambda I)x = b\). The residual \(r = b - (A - \lambda I)x \) is an eigenvector because \( (A - \lambda I)r = 0 \).

    If \( \lambda \) is not exact, use a loose stopping tolerance and Rayleigh-quotient iteration to refine \( \lambda \).

    [1] S.-C. T. Choi (2006). Iterative Methods for Singular Linear Equations and Least-Squares Problems, PhD thesis, ICME, Stanford University.

    [2] S.-C. T. Choi, C. C. Paige and M. A. Saunders. MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems, SIAM J. Sci. Comput. 33:4, 1810-1836, published electronically Aug 4, 2011.

    [3] S.-C. T. Choi and M. A. Saunders. Algorithm 937: MINRES-QLP for symmetric and Hermitian linear equations and least-squares problems, ACM Trans. Math. Softw. 40:2, Article 16 (Feb 2014), 12 pp. (pdf)


    02 May 2010: MATLAB implementation

    12 Sep 2013: f90 implementations (real and complex) version 27

    07 Jun 2018: Python implementation available from Yang Liu et al.