Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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.

References [Enhancements On Off] (What's this?)

  • 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
  • [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. $ \ast$ 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. $ \ast$ 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. $ \ast$ 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, 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. $ \ast$ 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. $ \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.
  • 10. $ \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.
  • [16] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422

Similar Articles

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