Methods for modifying matrix factorizations

Authors:
P. E. Gill, G. H. Golub, W. Murray and M. A. Saunders

Journal:
Math. Comp. **28** (1974), 505-535

MSC:
Primary 65F05

DOI:
https://doi.org/10.1090/S0025-5718-1974-0343558-6

MathSciNet review:
0343558

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In recent years, several algorithms have appeared for modifying the factors of a matrix following a rank-one change. These methods have always been given in the context of specific applications and this has probably inhibited their use over a wider field. In this report, several methods are described for modifying Cholesky factors. Some of these have been published previously while others appear for the first time. In addition, a new algorithm is presented for modifying the complete orthogonal factorization of a general matrix, from which the conventional *QR* factors are obtained as a special case. A uniform notation has been used and emphasis has been placed on illustrating the similarity between different methods.

**1.**1. R. H. Bartels, G. H. Golub & M. A. Saunders, "Numerical techniques in mathematical programming,"*Nonlinear Programming*(Proc. Sympos., Univ. of Wisconsin, Madison, Wis., 1970), Academic Press, New York, 1970, pp. 123-176. MR**42**#7277. MR**0272396 (42:7277)****[2]**J. M. Bennett, "Triangular factors of modified matrices,"*Numer. Math.*, v. 7, 1965, pp. 217-221. MR**31**#1766. MR**0177503 (31:1766)****[3]**D. K. Faddeev, V. N. Kublanovskaya & V. N. Faddeeva, "Sur les systèmes linéaires algébriques de matrices rectangulaires et mal-conditionnées,"*Programmation en Mathématiques Numériques*(Actes Colloq. Internat. C.N.R.S. No. 165, Besançon, 1966), Éditions Centre Nat. Recherche Sci., Paris, 1968, pp. 161-170. MR**37**#6017. MR**0230455 (37:6017)****2.**4. W. M. Gentleman,*Least Squares Computations by Givens Transformations Without Square Roots,*Department of Applied Analysis and Computer Science Report CSRR-2062, University of Waterloo, Waterloo, Ontario, 1972. MR**0329233 (48:7575)****3.**5. P. E. Gill & W. Murray,*A Numerically Stable Form of the Simplex Algorithm*, National Physical Laboratory, DNAM Report Number 87, Teddington, England, 1970.**4.**6. P. E. Gill & W. Murray, "Quasi-Newton methods for unconstrained optimization,"*J. Inst. Math. Appl.*, v. 9, 1972, pp. 91-108. MR**45**#9456. MR**0300410 (45:9456)****5.**7. P. E. Gill & W. Murray,*Two Methods For the Solution of Linearly Constrained and Unconstrained Optimization Problems*, National Physical Laboratory, DNAC Report Number 25, Teddington, England, 1972.**6.**8. G. H. Golub & M. A. Saunders, "Linear least squares and quadratic programming,"*Integer and Nonlinear Programming*, North-Holland, Amsterdam, 1970. MR**0437049 (55:9983)****7.**9. G. H. Golub & P. H. Styan,*Numerical Computations for Univariate Linear Models*, Computer Science Department Report Number CS-236-71, Stanford University, Stanford, California, 1971.**[10]**R. J. Hanson & C. L. Lawson, "Extensions and applications of the Householder algorithm for solving linear least squares problems,"*Math. Comp.*, v. 23, 1969, pp. 787-812. MR**41**#2905. MR**0258258 (41:2905)****[11]**R. S. Martin, G. Peters & J. H. Wilkinson, "The*QR*algorithm for real Hessenberg matrices,"*Handbook for Automatic Computation*, Vol. 2. Edited by J. H. Wilkinson and C. Reinsch, Springer-Verlag, Berlin and New York, 1971, pp. 359-371.**8.**12. W. Murray,*An Algorithm for Indefinite Quadratic Programming*, National Physical Laboratory, DNAC Report Number 1, Teddington, England, 1971.**[13]**G. Peters & J. H. Wilkinson, "The least squares problem and pseudo-inverses,"*Comput. J.*, v. 13, 1970, pp. 309-316.**9.**14. M. A. Saunders,*Large-Scale Linear Programming Using the Cholesky Factorization*, Computer Science Department Report Number CS-72-252, Stanford University, Stanford, California, 1972.**10.**15. M. A. Saunders,*Product Form of the Cholesky Factorization for Large-Scale Linear Programming*, Computer Science Department Report Number CS-72-301, Stanford University, Stanford, Calif., 1972.**[16]**J. H. Wilkinson,*The Algebraic Eigenvalue Problem*, Clarendon Press, Oxford, 1965. MR**32**#1894. MR**0184422 (32:1894)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F05

Retrieve articles in all journals with MSC: 65F05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1974-0343558-6

Article copyright:
© Copyright 1974
American Mathematical Society