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.

    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.

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

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


    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.