Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems

Full text

Pdf (2.58 MB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 35 , Issue 4 (February 2009) table of contents

Article No. 28

Year of Publication: 2009

ISSN:0098-3500

Authors

James Demmel	University of California, Berkeley
Yozo Hida	University of California, Berkeley
E. Jason Riedy	University of California, Berkeley
Xiaoye S. Li	Lawrence Berkeley National Laboratory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 92, Citation Count: 0

Additional Information:

abstract references 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/1462173.1462177 What is a DOI?

ABSTRACT

We present the algorithm, error bounds, and numerical results for extra-precise iterative refinement applied to overdetermined linear least squares (LLS) problems. We apply our linear system refinement algorithm to Björck’s augmented linear system formulation of an LLS problem. Our algorithm reduces the forward normwise and componentwise errors to O(ϵ_w), where ϵ_w is the working precision, unless the system is too ill conditioned. In contrast to linear systems, we provide two separate error bounds for the solution x and the residual r. The refinement algorithm requires only limited use of extra precision and adds only O(mn) work to the O(mn²) cost of QR factorization for problems of size m-by-n. The extra precision calculation is facilitated by the new extended-precision BLAS standard in a portable way, and the refinement algorithm will be included in a future release of LAPACK and can be extended to the other types of least squares problems.

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	Mario Arioli , Marc Baboulin , Serge Gratton, A Partial Condition Number for Linear Least Squares Problems, SIAM Journal on Matrix Analysis and Applications, v.29 n.2, p.413-433, March 2007 [doi>10.1137/050643088]
	2	Bailey, D. 2009. A Fortran-90 double-double precision library. http://crd.lbl.gov/~dhbailey/mpdist.
	3	Björck, Å. 1967. Iterative refinement of linear least squares solutions I. BIT 7, 257--278.
	4	Å. Björck, Component-wise perturbation analysis and error bounds for linear least squares solutions, BIT, v.31 n.2, p.238-244, 1991
	5	Björck, Å. 1996. Numerical Methods for Least Squares Problems. SIAM, Philadelphia, PA.
	6	Björck, Å. and Golub, G. 1967. Iterative refinement of linear least squares solution by Householder transformation (Algol programming). BIT 7, 322--337.
	7	Cucker, F., Diao, H., and Wei, Y. 2007. On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems. Math. Comput. 76, 258, 947--963.
	8	James Demmel , Yozo Hida , William Kahan , Xiaoye S. Li , Sonil Mukherjee , E. Jason Riedy, Error bounds from extra-precise iterative refinement, ACM Transactions on Mathematical Software (TOMS), v.32 n.2, p.325-351, June 2006 [doi>10.1145/1141885.1141894]
	9	Forsythe, G. E. and Moler, C. B. 1967. Computer Solution of Linear Algebraic Systems. Prentice-Hall, Englewood Cliffs, NJ.
	10	Gulliksson, M. 1994. Iterative refinement for constrained and weighted linear least squares. BIT 34, 2, 239--253.
	11	Nicholas J. Higham, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Transactions on Mathematical Software (TOMS), v.14 n.4, p.381-396, Dec. 1988 [doi>10.1145/50063.214386]
	12	Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996
	13	Kielbasinski, A. and Schwetlick, H. 1988. Numerische Lineare Algebra: Eine Computerorientierte Einführung. VEB Deutscher, Berlin.
	14	Langou, J., Langou, J., Luszczek, P., Kurzak, J., Buttari, A., and Dongarra, J. 2006. Exploiting the performance of 32 bit floating point arithmetic in obtaining 64 bit accuracy (revisiting iterative refinement for linear systems). Tech. rep., University of Tennessee, Knoxville, TN. June.
	15	Xiaoye S. Li , James W. Demmel , David H. Bailey , Greg Henry , Yozo Hida , Jimmy Iskandar , William Kahan , Suh Y. Kang , Anil Kapur , Michael C. Martin , Brandon J. Thompson , Teresa Tung , Daniel J. Yoo, Design, implementation and testing of extended and mixed precision BLAS, ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.152-205, June 2002 [doi>10.1145/567806.567808]
	16	Oettli, W. and Prager, W. 1964. Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer. Math. 6, 405--409.
	17	Reid, J. 2000. Implicit scaling of linear least squares problems. BIT 40, 1, 146--157.
	18	J. L. Rigal , J. Gaches, On the Compatibility of a Given Solution With the Data of a Linear System, Journal of the ACM (JACM), v.14 n.3, p.543-548, July 1967 [doi>10.1145/321406.321416]
	19	Stewart, G. W. 1977. On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM Rev. 19, 4, 634--662.
	20	Walden, B., Karlson, R., and J., S. 1995. Optimal backward perturbation bounds for the linear least squares problem. Numer. Lin. Alg. Appl. 2, 3, 271--286.
	21	Wampler, R. H. 1970. A report on the accuracy of some widely used least squares computer programs (in applications). J. Amer. Statist. Assoc. 65, 330, 549--565.