A stable algorithm for updating triangular factors under a rank one change
R. Fletcher and S. P. J. Matthews
Math. Comp. 45 (1985), 471-485
Full-text PDF Free Access
Similar Articles |
Abstract: An algorithm is presented for updating the LU factors of an matrix A, when A is changed by a matrix of rank one. The algorithm is based on the repeated use of triangular operations, and stability is obtained by allowing both row and column pivoting. The cost of the algorithm is approximately proportional to the maximum permitted depth for the pivot search. For well-conditioned matrices a maximum depth of 3 is sufficient to ensure stability. For substantially rank deficient matrices it is theoretically possible that pivots of any depth may be required, but in practice we find that a value of 5 is adequate. We suggest a pivot strategy, based on minimizing a growth bound, which penalizes deep pivots and imposes a maximum depth of pivot through a default value.
On well-behaved problems the asymptotic cost of the update is observed to be approximately compared with (or worse) for updating orthogonal factors. Given the accuracy obtained by the new algorithm, we feel that there are many applications in which the lower cost of triangular factors can be exploited. Comparison with ab initio factorization indicates that for updating triangular factors is advantageous.
M. Bennett, Triangular factors of modified matrices, Numer.
Math. 7 (1965), 217–221. MR 0177503
W. Daniel, W.
B. Gragg, L.
Kaufman, and G.
W. Stewart, Reorthogonalization and stable
algorithms for updating the Gram-Schmidt 𝑄𝑅
factorization, Math. Comp.
30 (1976), no. 136, 772–795. MR 0431641
(55 #4638), http://dx.doi.org/10.1090/S0025-5718-1976-0431641-8
Fletcher and S.
P. J. Matthews, Stable modification of explicit 𝐿𝑈
factors for simplex updates, Math. Programming 30
(1984), no. 3, 267–284. MR 769232
E. Gill, G.
H. Golub, W.
Murray, and M.
A. Saunders, Methods for modifying matrix
factorizations, Math. Comp. 28 (1974), 505–535. MR 0343558
(49 #8299), http://dx.doi.org/10.1090/S0025-5718-1974-0343558-6
H. Wilkinson, The algebraic eigenvalue problem, Clarendon
Press, Oxford, 1965. MR 0184422
- J. M. Bennett, "Triangular factors of modified matrices," Numer. Math., v. 7, 1965, pp. 217-221. MR 0177503 (31:1766)
- J. W. Daniel, W. B. Gragg, L. Kaufman & G. W. Stewart, "Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization," Math. Comp., v. 30, 1976, pp. 772-795. MR 0431641 (55:4638)
- R. Fletcher & S. P. J. Matthews, Stable Modification of Explicit LU Factors for Simplex Updates, Department of Mathematics Report NA/64, Dundee University, 1983. MR 769232 (86e:90069)
- P. E. Gill, G. H. Golub, W. Murray & M. A. Saunders, "Methods for modifying matrix factorizations," Math. Comp., v. 28, 1974, pp. 505-535. MR 0343558 (49:8299)
- J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 0184422 (32:1894)
Retrieve articles in Mathematics of Computation
Retrieve articles in all journals
Rank one update,
© Copyright 1985
American Mathematical Society