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

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. $ \ast$ 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. $ \ast$ 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. $ \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. $ \ast$ 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. $ \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. $ \ast$ 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. $ \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] 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. $ \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 32 #1894. MR 0184422 (32:1894)

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

American Mathematical Society