MINRES: Sparse Symmetric Equations

• AUTHORS: C. C. Paige, M. A. Saunders.
• CONTRIBUTORS: Sou-Cheng Choi
• CONTENTS: Implementation of a conjugate-gradient type method for solving sparse linear equations: Solve Ax = b or (A - sI)x = b. 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

  min ||Ax - b|| or min ||(A - sI)x - b||. 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 MINRESQLP (see PhD dissertation of Sou-Cheng Choi).

  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.

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

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

• Matlab files
• Fortran 77 files
• Fortran 90 files