Reorthogonalization and stable algorithms for updating the Gram-Schmidt 𝑄𝑅 factorization

Daniel, J. W.; Gragg, W. B.; Kaufman, L.; Stewart, G. W.

doi:10.1090/S0025-5718-1976-0431641-8

Reorthogonalization and stable algorithms for updating the Gram-Schmidt $QR$ factorization
HTML articles powered by AMS MathViewer

by J. W. Daniel, W. B. Gragg, L. Kaufman and G. W. Stewart PDF

Math. Comp. 30 (1976), 772-795 Request permission

Abstract:

Numerically stable algorithms are given for updating the Gram-Schmidt QR factorization of an $m \times n$ matrix $A\;(m \geqslant n)$ when A is modified by a matrix of rank one, or when a row or column is inserted or deleted. The algorithms require $O(mn)$ operations per update, and are based on the use of elementary two-by-two reflection matrices and the Gram-Schmidt process with reorthogonalization. An error analysis of the reorthogonalization process provides rigorous justification for the corresponding ALGOL procedures.

References

George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders, Methods for modifying matrix factorizations, Math. Comp. 28 (1974), 505–535. MR 343558, DOI 10.1090/S0025-5718-1974-0343558-6
Philip E. Gill, Walter Murray, and Michael A. Saunders, Methods for computing and modifying the $LDV$ factors of a matrix, Math. Comp. 29 (1975), no. 132, 1051–1077. MR 388754, DOI 10.1090/S0025-5718-1975-0388754-8
W. B. Gragg and G. W. Stewart, A stable variant of the secant method for solving nonlinear equations, SIAM J. Numer. Anal. 13 (1976), no. 6, 889–903. MR 433856, DOI 10.1137/0713070
Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
Charles L. Lawson and Richard J. Hanson, Solving least squares problems, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. MR 0366019

Handbook for Automatic Computation

Description of ALGOL

G. W. Stewart, Introduction to matrix computations, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0458818
J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422