Systems Optimization Laboratory
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:
|
