Methods for modifying matrix factorizations
Authors:
P. E. Gill, G. H. Golub, W. Murray and M. A. Saunders
Journal:
Math. Comp. 28 (1974), 505535
MSC:
Primary 65F05
MathSciNet review:
0343558
Fulltext 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 rankone 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. 123176. MR 42 #7277. MR 0272396 (42:7277)
 [2]
J. M. Bennett, "Triangular factors of modified matrices," Numer. Math., v. 7, 1965, pp. 217221. 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 malconditionné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. 161170. 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 CSRR2062, 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, "QuasiNewton methods for unconstrained optimization," J. Inst. Math. Appl., v. 9, 1972, pp. 91108. 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, NorthHolland, 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 CS23671, 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. 787812. 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, SpringerVerlag, Berlin and New York, 1971, pp. 359371.
 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 pseudoinverses," Comput. J., v. 13, 1970, pp. 309316.
 9.
14. M. A. Saunders, LargeScale Linear Programming Using the Cholesky Factorization, Computer Science Department Report Number CS72252, Stanford University, Stanford, California, 1972.
 10.
15. M. A. Saunders, Product Form of the Cholesky Factorization for LargeScale Linear Programming, Computer Science Department Report Number CS72301, Stanford University, Stanford, Calif., 1972.
 [16]
J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 32 #1894. MR 0184422 (32:1894)
 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. 123176. MR 42 #7277. MR 0272396 (42:7277)
 [2]
 J. M. Bennett, "Triangular factors of modified matrices," Numer. Math., v. 7, 1965, pp. 217221. 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 malconditionné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. 161170. 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 CSRR2062, 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, "QuasiNewton methods for unconstrained optimization," J. Inst. Math. Appl., v. 9, 1972, pp. 91108. 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, NorthHolland, 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 CS23671, 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. 787812. 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, SpringerVerlag, Berlin and New York, 1971, pp. 359371.
 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 pseudoinverses," Comput. J., v. 13, 1970, pp. 309316.
 9.
 14. M. A. Saunders, LargeScale Linear Programming Using the Cholesky Factorization, Computer Science Department Report Number CS72252, Stanford University, Stanford, California, 1972.
 10.
 15. M. A. Saunders, Product Form of the Cholesky Factorization for LargeScale Linear Programming, Computer Science Department Report Number CS72301, 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
DOI:
http://dx.doi.org/10.1090/S00255718197403435586
PII:
S 00255718(1974)03435586
Article copyright:
© Copyright 1974
American Mathematical Society
