Methods for computing and modifying the 𝐿𝐷𝑉 factors of a matrix

Gill, Philip E.; Murray, Walter; Saunders, Michael A.

doi:10.1090/S0025-5718-1975-0388754-8

Methods for computing and modifying the $LDV$ factors of a matrix
HTML articles powered by AMS MathViewer

by Philip E. Gill, Walter Murray and Michael A. Saunders PDF

Math. Comp. 29 (1975), 1051-1077 Request permission

Abstract:

Methods are given for computing the LDV factorization of a matrix B and modifying the factorization when columns of B are added or deleted. The methods may be viewed as a means for updating the orthogonal (LQ) factorization of B without the use of square roots. It is also shown how these techniques lead to two numerically stable methods for updating the Cholesky factorization of a matrix following the addition or subtraction, respectively, of a matrix of rank one. The first method turns out to be one given recently by Fletcher and Powell; the second method has not appeared before.

References

On the Modification of

Factorizations

W. Morven Gentleman, Least squares computations by Givens transformations without square roots, J. Inst. Math. Appl. 12 (1973), 329–336. MR 329233, DOI 10.1093/imamat/12.3.329
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
Eli Hellerman and Dennis Rarick, Reinversion with the preassigned pivot procedure, Math. Programming 1 (1971), 195–216. MR 293819, DOI 10.1007/BF01584086
Donald J. Rose and Ralph A. Willoughby (eds.), Sparse matrices and their applications, Plenum Press, New York-London, 1972. MR 0331743

Product Form of the Cholesky Factorization for Large-Scale Linear Programming