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 Free Access

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.

- 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** - John M. Bennett,
*Triangular factors of modified matrices*, Numer. Math.**7**(1965), 217–221. MR**177503**, DOI https://doi.org/10.1007/BF01436076 - 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** - W. Morven Gentleman,
*Least squares computations by Givens transformations without square roots*, J. Inst. Math. Appl.**12**(1973), 329–336. MR**329233**
$\ast$ 5. P. E. Gill & W. Murray, - P. E. Gill and W. Murray,
*Quasi-Newton methods for unconstrained optimization*, J. Inst. Math. Appl.**9**(1972), 91–108. MR**300410**
$\ast$ 7. P. E. Gill & W. Murray, - 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**
$\ast$ 9. G. H. Golub & P. H. Styan, - 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**258258**, DOI https://doi.org/10.1090/S0025-5718-1969-0258258-9
R. S. Martin, G. Peters & J. H. Wilkinson, "The - J. H. Wilkinson,
*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422**

*A Numerically Stable Form of the Simplex Algorithm*, National Physical Laboratory, DNAM Report Number 87, Teddington, England, 1970.

*Two Methods For the Solution of Linearly Constrained and Unconstrained Optimization Problems*, National Physical Laboratory, DNAC Report Number 25, Teddington, England, 1972.

*Numerical Computations for Univariate Linear Models*, Computer Science Department Report Number CS-236-71, Stanford University, Stanford, California, 1971.

*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. $\ast$ 12. W. Murray,

*An Algorithm for Indefinite Quadratic Programming*, National Physical Laboratory, DNAC Report Number 1, Teddington, England, 1971. G. Peters & J. H. Wilkinson, "The least squares problem and pseudo-inverses,"

*Comput. J.*, v. 13, 1970, pp. 309-316. $\ast$ 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. $\ast$ 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.

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

Retrieve articles in all journals with MSC: 65F05

Additional Information

Article copyright:
© Copyright 1974
American Mathematical Society