Systems Optimization Laboratory
Stanford, CA 94305-4121 USA
|
CRAIG: Sparse Equations
- AUTHORS:
Chris Paige,
Michael Saunders.
- CONTRIBUTORS:
Dominique Orban.
- CONTENTS: Implementation of a conjugate-gradient type method
for solving sparse linear equations
\begin{align*}
\text{Solve } & Ax=b
\\ \text{minimize } \|x\| \text{ s.t. } & Ax=b,
\end{align*}
where the matrix \(A\) may be square or rectangular
and may have any rank, as long as \(Ax=b\) is compatible.
\(A\) is represented by a routine for computing \(Av\) and \(A^T u\)
for given vectors \(v\) and \(u\).
The method is based on the Golub-Kahan bidiagonalization
process. It is algebraically equivalent to applying CG
to the symmetric system
\(
A A^T y = b
\)
and setting \(x = A^T y\),
but it has better numerical properties, especially if
\(A\) is ill-conditioned.
For CRAIG's approximate solutions \(x_k\),
the norms \(\|x_k\|\) increase monotonically
and the errors \(\|x - x_k\|\) decrease monotonically.
If \(A\) is symmetric, use
SYMMLQ,
MINRES,
or MINRES-QLP.
If \(Ax = b\) has no solution (is incompatible), use
LSQR
or LSMR.
- REFERENCES:
C. C. Paige and M. A. Saunders,
LSQR: An algorithm for sparse linear equations and sparse least squares,
TOMS 8(1), 43-71 (1982). (See p58.)
- RELEASE:
15 Aug 2014: This webpage created.
craigSOL.m implemented to complement lsqrSOL.m.
19 Aug 2014: Beware: the estimate of cond(A) seems too high
and may cause early termination. If so, it is
easy to disable the stopping tests involving Acond.
28 Aug 2014: Fixed glitches found by Dominique Orban.
DOWNLOADS:
|
