Methods for modifying matrix factorizations
HTML articles powered by AMS MathViewer
- by P. E. Gill, G. H. Golub, W. Murray and M. A. Saunders PDF
- Math. Comp. 28 (1974), 505-535 Request permission
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
- 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 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 du Centre National de la Recherche Scientifique (CNRS), 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, A Numerically Stable Form of the Simplex Algorithm, National Physical Laboratory, DNAM Report Number 87, Teddington, England, 1970.
- 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, Two Methods For the Solution of Linearly Constrained and Unconstrained Optimization Problems, National Physical Laboratory, DNAC Report Number 25, Teddington, England, 1972.
- 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, Numerical Computations for Univariate Linear Models, Computer Science Department Report Number CS-236-71, Stanford University, Stanford, California, 1971.
- 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 10.1090/S0025-5718-1969-0258258-9 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. $\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.
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Additional Information
- © Copyright 1974 American Mathematical Society
- Journal: Math. Comp. 28 (1974), 505-535
- MSC: Primary 65F05
- DOI: https://doi.org/10.1090/S0025-5718-1974-0343558-6
- MathSciNet review: 0343558