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