Algorithm 583: LSQR: Sparse Linear Equations and Least Squares Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithm 583: LSQR: Sparse Linear Equations and Least Squares Problems

Full text

Pdf (716 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 8 , Issue 2 (June 1982) table of contents

Pages: 195 - 209

Year of Publication: 1982

ISSN:0098-3500

Authors

Christopher C. Paige	School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2K6
Michael A. Saunders	Department of Operations Research, Stanford University, Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 108, Citation Count: 14

Additional Information:

appendices and supplements references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/355993.356000 What is a DOI?

APPENDICES and SUPPLEMENTS

LSQR (583.gz) (11 KB)

overdetermined or underdetermined sparse systems of linear equations, sparse least squares problems, and damped sparse least squares problems
Gams: D9a1

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BJORCK, }k. A bidlagonahzation algorithm for solving ill-posed systems of linear equahons Rep LITH-MAT-R-80-33, Dep. Mathematics, Linkopmg Univ., Lmkoping, Sweden, 1980.
	2	ELDI~N, L. Algorithms for the regularization of ill-conditioned least squares problems BIT 17 (1977), 134-145.
	3	HESTENES, M.R, AND STIEFEL, E Methods of conjugate gradients for solving hneax systems. J Res. N.B.S. 49 (1952), 409-436.
	4	LAWSON, C.L, AND HANSON, R.J Solwng Least Squares Problems. Prentice-Hall, Englewood Cliffs, N.J., 1974.
	5	C. L. Lawson , R. J. Hanson , F. T. Krogh , D. R. Kincaid, Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage [F1], ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.324-325, Sept. 1979 [doi>10.1145/355841.355848]
	6	Christopher C. Paige , Michael A. Saunders, LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares, ACM Transactions on Mathematical Software (TOMS), v.8 n.1, p.43-71, March 1982 [doi>10.1145/355984.355989]
	7	SMITH, G., AND CAMPBELL, V. A critique of some ridge regression methods. J. Am. Star. Assoc. 75, 369 (March 1980), 74-81
	8	VARAH, J.M A practical examination of some numerical methods for linear discrete ill-posed problems SIAM Rev. 21 (1979), 100-111.
	9	WOLD, S., WOLD, H., DUNN, W.J., AND RUHE, A. The coUinearity problem in linear and nonlinear regression. The partial least squares (PLS) approach to generalized inverses. Rep. UMINF-83.80, Univ. Ume~, Ume~, Sweden, 1980.
	10	Christopher C. Paige , Michael A. Saunders, LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares, ACM Transactions on Mathematical Software (TOMS), v.8 n.1, p.43-71, March 1982 [doi>10.1145/355984.355989]
	11	C. L. Lawson , R. J. Hanson , F. T. Krogh , D. R. Kincaid, Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage [F1], ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.324-325, Sept. 1979 [doi>10.1145/355841.355848]

CITED BY 14

	D. Calvetti , L. Reichel , A. Shuibi, Invertible smoothing preconditioners for linear discrete ill-posed problems, Applied Numerical Mathematics, v.54 n.2, p.135-149, July 2005
	Christopher C. Paige , Michael A. Saunders, LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares, ACM Transactions on Mathematical Software (TOMS), v.8 n.1, p.43-71, March 1982
	Doron Chen , Daniel Cohen-Or , Olga Sorkine , Sivan Toledo, Algebraic analysis of high-pass quantization, ACM Transactions on Graphics (TOG), v.24 n.4, p.1259-1282, October 2005
	G. Landi, A Truncated Lagrange Method for Total Variation-Based Image Restoration, Journal of Mathematical Imaging and Vision, v.28 n.2, p.113-123, June 2007
	James Baglama , Lothar Reichel, Decomposition methods for large linear discrete ill-posed problems, Journal of Computational and Applied Mathematics, v.198 n.2, p.332-343, 15 January 2007
	Ladislav Kavan , Rachel McDonnell , Simon Dobbyn , Jiří Žára , Carol O'Sullivan, Skinning arbitrary deformations, Proceedings of the 2007 symposium on Interactive 3D graphics and games, April 30-May 02, 2007, Seattle, Washington
	H. L. Zou , Y. T. Lee, Constraint-based beautification and dimensioning of 3D polyhedral models reconstructed from 2D sketches, Computer-Aided Design, v.39 n.11, p.1025-1036, November, 2007
	Deng Cai , Xiaofei He , Jiawei Han, Spectral regression: a unified subspace learning framework for content-based image retrieval, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany
	Deng Cai , Xiaofei He , Jiawei Han, SRDA: An Efficient Algorithm for Large-Scale Discriminant Analysis, IEEE Transactions on Knowledge and Data Engineering, v.20 n.1, p.1-12, January 2008
	L. Reichel , H. Sadok , A. Shyshkov, Greedy Tikhonov regularization for large linear ill-posed problems, International Journal of Computer Mathematics, v.84 n.8, p.1151-1166, August 2007
	Dmitry Danilov , Jan R. Magnus, On the estimation of a large sparse Bayesian system: The Snaer program, Computational Statistics & Data Analysis, v.52 n.9, p.4203-4224, May, 2008
	Deng Cai , Xiaofei He , Wei Vivian Zhang , Jiawei Han, Regularized locality preserving indexing via spectral regression, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Oliver Baur, Tailored least-squares solvers implementation for high-performance gravity field research, Computers & Geosciences, v.35 n.3, p.548-556, March, 2009
	Hillel Bar-Gera, Primal Method for Determining the Most Likely Route Flows in Large Road Networks, Transportation Science, v.40 n.3, p.269-286, August 2006

INDEX TERMS

Primary Classification:
G. Mathematics of Computing

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.1 Numerical Algorithms and Problems
Subjects: Computations on matrices

G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.3 Numerical Linear Algebra
Subjects: Sparse, structured, and very large systems (direct and iterative methods); Linear systems (direct and iterative methods)
G.1.6 Optimization
Subjects: Least squares methods; Gradient methods

Collaborative Colleagues:

Christopher C. Paige: colleagues

Michael A. Saunders: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player