Systems Optimization Laboratory
Stanford, CA 94305-4121 USA
|
LSQR: Sparse Equations and Least Squares
- AUTHORS:
Chris Paige,
Michael Saunders.
- CONTRIBUTORS: James Howse, Michael Friedlander,
John Tomlin, Miha Grcar, Jeffery Kline, Dominique Orban.
- CONTENTS: Implementation of a conjugate-gradient type method
for solving sparse linear equations and
sparse least-squares problems:
\begin{align*}
\text{Solve } & Ax=b
\\ \text{or minimize } & \|Ax-b\|^2
\\ \text{or minimize } & \|Ax-b\|^2 + \lambda^2 \|x\|^2
\end{align*}
where the matrix \(A\) may be square or rectangular
(over-determined or under-determined), and may have any rank.
It is represented by a routine for computing \(Av\) and \(A^T u\)
for given vectors \(v\) and \(u\).
The scalar \(\lambda\) is a damping parameter.
If \(\lambda > 0\), the solution is "regularized" in the sense that
a unique solution always exists, and \(\|x\|\) is bounded.
The method is based on the Golub-Kahan bidiagonalization
process. It is algebraically equivalent to applying MINRES
to the normal equation
\(
(A^T A + \lambda^2 I) x = A^T b,
\)
but has better numerical properties, especially if
\(A\) is ill-conditioned.
NOTE: LSQR reduces \(\|r\|\) monotonically
(where \(r = b - Ax\) if \(\lambda=0\)). If you are likely to terminate
iterations early, LSMR may be preferable
because it reduces both \(\|r\|\) and \(\|A^T r\|\) monotonically.
If \(A\) is symmetric, it should be more efficient
to use SYMMLQ,
MINRES,
or MINRES-QLP.
- 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).
C. C. Paige and M. A. Saunders,
Algorithm 583; LSQR: Sparse linear equations and least-squares problems,
TOMS 8(2), 195-209 (1982).
- RELEASE:
f77 and Matlab files are well tested.
C, f90, C++ versions are Beta.
Windows DLL and .NET (C#) versions are Beta.
|
