LSQR: Sparse Equations and Least Squares

• AUTHORS: C. C. Paige, M. A. Saunders.
• CONTRIBUTORS: James Howse, Michael Friedlander, Eric Badel, John Tomlin, Miha Grcar
• CONTENTS: Implementation of a conjugate-gradient type method for solving sparse linear equations and sparse least-squares problems: Solve Ax = b
  or minimize || Ax - b ||²
  or minimize || Ax - b ||² + d² ||x||². 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'u for given vectors v and u.

  The scalar d is a damping parameter. If d > 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 the symmetric conjugate gradient (CG) method to the normal equations, (A'A + d² I) x = A'b, but has better numerical properties, especially if A is ill-conditioned.

  If A is symmetric, it should be more efficient to use SYMMLQ.

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

• Fortran 77 files
• Matlab files
• C files 1: Contributed Sep 1999 by James Howse (jhowse@lanl.gov), LANL.
  An elaborate implementation with memory management.
• C files 2: Contributed Aug 2007 by Michael Friedlander, UBC.
  A more direct line-by-line translation from f77.
• Fortran 90 files 1: Contributed Sep 2007 by Eric Badel (badel@nancy.inra.fr), LERMAB, INRA.
  Line-by-line translation of f77 files.
  Revised 19 Sep 2007.
• Fortran 90 files 2: Second-generation f90 implementation. Separate modules are used for LSQR, Check routines, and example Test problems.
  Contributed Sep 2007 by Michael Saunders (saunders@stanford.edu).
  Revised 24 Oct 2007, 19 Dec 2008.
• C++ files: Contributed Oct 2007 by John Tomlin (tomlin@yahoo-inc.com), Yahoo! Research.
  C++ translation of C files in lsqr/c/clsqr1.zip.
• Windows DLL and .NET files: Contributed Oct 2007 by Miha Grcar (miha.grcar@ijs.si), Jozef Stefan Institute.
  Windows DLL and .NET (C#) wrappers for LSQR based on the C++ version of LSQR.
• Python files from Jeffery Kline