Golang implementation of LSQR for solving sparse linear equations and sparse least-squares problems.
Implementation in go based on the fortran77 version in : https://web.stanford.edu/group/SOL/software/lsqr/
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:
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.
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.
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).
DOWNLOADS: Fortran 77 files : https://web.stanford.edu/group/SOL/software/lsqr/lsqr-f77.zip