Systems Optimization Laboratory

LSQR: Sparse Equations and Least Squares

• AUTHORS: Chris Paige, Michael Saunders.
• CONTRIBUTORS: James Howse, Michael Friedlander, John Tomlin, Miha Grcar, Jeffery Kline, Dominique Orban, Austin Benson, Victor Minden.
• 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 CG 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$$). This is desirable on compatible systems $$Ax=b$$. On least-squares problems, if an approximate solution is acceptable (stopping tolerances quite large), LSMR may be a preferable solver because it reduces both $$\|r\|$$ and $$\|A^T r\|$$ monotonically and may be able to terminate significantly earlier.

If $$A$$ is symmetric, use SYMMLQ, MINRES, or MINRES-QLP.

If $$A$$ has low column rank and $$\lambda=0$$, the solution is not unique. LSQR returns the solution of minimum length. Thus for under-determined systems, it solves the problem $$\min \|x\| \text{ subject to } Ax=b$$. More generally, it solves the problem $$\min \|x\| \text{ subject to } A^T Ax=A^T b$$, where $$A$$ may have any shape or rank.

For $$\min \|x\| \text{ subject to } Ax=b$$, consider using CRAIG.

• 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, C++ versions are Beta.
Windows DLL and .NET (C#) versions are Beta.
26 Oct 2012: f90 test program updated.
05 Aug 2013: Complex f90 version added.