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.**R. H. Bartels, G. H. Golub, and 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**0272396****[2]**John M. Bennett,*Triangular factors of modified matrices*, Numer. Math.**7**(1965), 217–221. MR**0177503**, https://doi.org/10.1007/BF01436076**[3]**D. K. Faddeev, V. N. Kublanovskaya, and 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 (French, with English summary). MR**0230455****2.**W. Morven Gentleman,*Least squares computations by Givens transformations without square roots*, J. Inst. Math. Appl.**12**(1973), 329–336. MR**0329233****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.**P. E. Gill and W. Murray,*Quasi-Newton methods for unconstrained optimization*, J. Inst. Math. Appl.**9**(1972), 91–108. MR**0300410****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.**G. H. Golub and M. A. Saunders,*Linear least squares and quadratic programming*, Integer and nonlinear programming, North-Holland, Amsterdam, 1970, pp. 229–256. MR**0437049****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]**Richard J. Hanson and Charles L. Lawson,*Extensions and applications of the Householder algorithm for solving linear least squares problems*, Math. Comp.**23**(1969), 787–812. MR**0258258**, https://doi.org/10.1090/S0025-5718-1969-0258258-9**[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**0184422**

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