Stanford
MS&E
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, Matthieu Gomez, Tim Holy.
  • 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.
    30 Sep 2015: Link to Julia version added (Matthieu Gomez and Tim Holy).
    05 Jul 2016: Link to second C++ implementation added (Tom Vercauteren).

DOWNLOADS