Systems Optimization Laboratory

MINRES: Sparse Symmetric Equations

• AUTHORS: C. C. Paige, M. A. Saunders.
• CONTRIBUTORS: Sou-Cheng Choi, Dominique Orban, Umberto Emanuele Villa, Danielle Maddix
• 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].

• 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.