SOL Logo

Systems Optimization Laboratory

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

Huang Engineering Center

Stanford, CA 94305-4121  USA

MINRES: Sparse Symmetric Equations

  • AUTHORS: C. C. Paige, M. A. Saunders.
  • CONTRIBUTORS: Sou-Cheng Choi, Dominique Orban, Umberto Emanuele Villa.
  • CONTENTS: Implementation of a conjugate-gradient type method for solving sparse linear equations:  Solve \begin{align*} Ax = b \ \text{ or } \ (A - sI)x = b. \end{align*} The matrix \(A - sI\) must be symmetric but it may be definite or indefinite or singular. The scalar \(s\) is a shifting parameter -- it may be any number. The method is based on Lanczos tridiagonalization. You may provide a preconditioner, but it must be positive definite.

    MINRES is really solving one of the least-squares problems \begin{align*} \text{minimize } \|Ax - b\| \ \text{ or } \ \|(A - sI)x - b\|. \end{align*} If \(A\) is singular (and \(s = 0\)), MINRES returns a least-squares solution with small \(\|Ar\|\) (where \(r = b - Ax\)), but in general it is not the minimum-length solution. To get the min-length solution, use MINRES-QLP [2,3].

    Similarly if \(A - sI\) is singular.

    If \(A\) is symmetric (and \(A - sI\) is nonsingular), SYMMLQ may be slightly more reliable.

    If \(A\) is unsymmetric, use LSQR.

    MINRES is suitable for any symmetric \(A\), including positive definite systems. It might terminate considerably sooner than CG [4].

    [1] C. C. Paige and M. A. Saunders (1975). Solution of sparse indefinite systems of linear equations, SIAM J. Numerical Analysis 12, 617-629.

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

    [3] 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.

    [4] David Chin-Lung Fong and Michael Saunders. CG versus MINRES: An empirical comparison, SQU Journal for Science, 17:1 (2012), 44-62.


    22 Jul 2003: f77 files derived from f77 version of SYMMLQ. Preconditioning permitted; singular systems not.

    17 Oct 2003: MATLAB files derived from f77 version. Singular systems allowed.

    11 Oct 2007: f90 files derived from f77 version.

    04 Dec 2007: f90 version allows singular systems.

    11 May 2009: Matlab version updated following comments from Jeffery Kline.

    02 Sep 2011: Matlab version: Fixed bug in gmax, gmin initialization (David Fong). Also fixed updating of ynorm by computing ynorm = norm(x) (sic) directly. Same changes are needed in the other versions.

    11 Apr 2012: C++ version contributed by Umberto Villa.

    18 Apr 2012: C++ version contributed by Umberto Villa.