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, Danielle Maddix, Shaked Regev.
  • 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 an SPD preconditioner M. (Matlab version minres20.zip allows for an indefinite M to cause graceful exit and possible re-entry with a more positive-definite M.)

    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 or LSMR..

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

  • REFERENCES:
    [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.

  • RELEASE:

    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 tminres-0.1.zip contributed by Umberto Villa.

    18 Apr 2012: C++ version tminres-0.2.zip contributed by Umberto Villa.

    04 Jun 2015: Matlab version minresReorthog.zip contributed by Danielle Maddix. This version allows local reorthogonalization via input parameter localSize. The aim is to allow MINRES to be comparable to GMRES while preserving symmetry. On symmetric systems, if GMRES (without restarts) needs \(k\) iterations, MINRES with \( \text{localSize} \ge k\) should need no more than \(k\) iterations.
    This version does not work with a preconditioner.

    30 Apr 2020: Matlab minres overhauled (see minres20.zip below). New features:

    • x0 can be input.
    • Preconditioner M may need solves (precon=1, \(My=x\)) or products (precon=2, \(y=Mx\)).
      NOTE: For precon=1, consider Mfac = decomposition(M,...); and input M=Mfac.
    • The main stopping rule requires the residual \(r = b-Ax\) to be small enough
      (not the residual for the preconditioned system).
      This is as the user expects, and remains efficient even though only the
      preconditioned residual norm can be updated cheaply.
      The rule \( \|r_k\| \le (\|A\| \|x_k\| + \|b\|)*rtol \) shuts down earlier than the
      common rule \( \|r_k\| \le \|b\|*rtol \), but is justified by the backward error.
    • Automatic preconditioners SSAI, Mchol, Mldl, Mminres2, Mminres3 are provided for the case where \(A\) is an explicit sparse matrix. Mminres2 and Mminres3 could be adapted to allow \(A\) to be an operator. Example drivers are provided for testing each preconditioner on definite and indefinite matrices from SuiteSparse.

    15 May 2020: minres20.zip updated slightly.

    16 Jun 2020: minres20.zip updated. New readme.txt. New quick tests testSPD.m and testSID.m.


DOWNLOADS: