A modification to the LINPACK downdating algorithm. (English) Zbl 0718.65014
A LINPACK downdating algorithm is modified by interleaving its two different phases, the forward solution of a triangular system and the backward sweep of Givens rotation, to yield a new forward method for finding the Cholesky decomposition of \({\mathfrak R}^ T{\mathfrak R}-{\mathfrak zz}^ T\). It is shown that the new algorithm saves 40 percent purely redundant operations of the original one and is more accurate than the old one provide that n is fairly large.
The new algorithm is the best choice in general for the downdating problem. In addition, various other downdating algorithms are rederived and analyzed under a uniform framework. Some downdating examples having exact answer and their testing results are presented.
The new algorithm is the best choice in general for the downdating problem. In addition, various other downdating algorithms are rederived and analyzed under a uniform framework. Some downdating examples having exact answer and their testing results are presented.
Reviewer: Shenquan Xie (Xiangtan)
MSC:
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 15A23 | Factorization of matrices |
Keywords:
fast hyperbolic rotation; LINPACK downdating algorithm; triangular system; Givens rotation; Cholesky decomposition; testing resultsSoftware:
LINPACKReferences:
| [1] | S. T. Alexander, C.-T. Pan and R. J. Plemmons,Analysis of a recursive least squares hyperbolic rotation algorithm for signal processing, Lin. Alg. Appl., 1988, 98, 3–40. · Zbl 0639.94004 · doi:10.1016/0024-3795(88)90158-9 |
| [2] | Å. Björck,Error analysis of least squares algorithms, Report, LiTH-MAT-R-1988-22, Linköping, Sweden. |
| [3] | A. W. Bojanczyk, R. P. Brent, P. Van Dooren and F. R. de Hoog,A note on downdating the Cholesky factorization, SIAM. Sci. Stat. Comp., 1987, 8, 201–221. |
| [4] | A. W. Bojanczyk, R. P. Brent, and F. R. de Hoog,QR factorization of Toeplitz matrices, Numer. Math., 1986, 81–94. · Zbl 0574.65019 |
| [5] | J. R. Bunch,The weak and strong stability of algorithms in numerical linear algebra, Lin. Alg. Appl., 1987, 88/89, 49–66. · Zbl 0652.65032 · doi:10.1016/0024-3795(87)90102-9 |
| [6] | N. A. Carlson,Fast triangular factorization of the square root filter, AIAA J. 1973, 11, No. 9, 1259–1265. · doi:10.2514/3.6907 |
| [7] | J. M. Chambers,Regression updating, J. Amer. Stat. Assn., 1971, 66, 744–748. · doi:10.2307/2284221 |
| [8] | J. Chun, T. Kailath and H. Lev-Ari,Fast parallel algorithms for QR and triangular factorization, SIAM. Sci. Stat. Comp., 1988, 8, No. 6, 899–913. · Zbl 0632.65023 · doi:10.1137/0908073 |
| [9] | J. Dongarra, J. R. Bunch, C. B. Moler and G. W. Stewart,LINPACK Users’ Guide, SIAM Publication, Philadelphia, 1978. · Zbl 0476.68025 |
| [10] | R. Fletcher and M. J. D. Powell,On the modification of LDL T factorizations, Math. Comp., 1974, 28, 1067–1087. · Zbl 0293.65018 |
| [11] | W. M. Gentleman,Least squares computations by Givens transformations without square roots, J. Inst. Math. Appl., 1973, 12, 329–336. · Zbl 0289.65020 · doi:10.1093/imamat/12.3.329 |
| [12] | P. E. Gill, G. H. Golub, W. Murray and M. A. Saunders,Methods for modifying matrix factorizations, Math. Comp., 1974, 28, 505–535. · Zbl 0289.65021 · doi:10.1090/S0025-5718-1974-0343558-6 |
| [13] | P. E. Gill and W. Murray,A numerically stable form of the simplex method, Lin. Alg. Appl., 1973, 7, 99–138. · Zbl 0255.65029 · doi:10.1016/0024-3795(73)90047-5 |
| [14] | P. E. Gill and W. Murray,Modification of matrix after a rank one change, Proc. Conf.On the State of Art in Numerical Analysis at Univ. of York, Academic Press, N.Y., 1977, 55–83. |
| [15] | G. H. Golub,Matrix decompositions and statistical calculations, in R. C. Milton and J. A. Nelder (eds.),Statistical Computation, Academic Press, N.Y., 1969, 365–395. |
| [16] | G. H. Golub and C. Van Loan,Matrix Computation, Johns Hopkins Press, Baltimore, M.D., 1983. · Zbl 0559.65011 |
| [17] | S. Hammarling,A note on modification to the Givens plane rotations, J. Inst. Math. Appl., 1974, 13, 215–218. · Zbl 0278.65037 |
| [18] | C. L. Lawson and R.J. Hanson,Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, N.J., 1974. · Zbl 0860.65028 |
| [19] | B. N. Parlett,The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, N.J., 1980. · Zbl 0431.65017 |
| [20] | C.-T. Pan,Hyperbolic Rotations for Downdating the Cholesky Factorization with Application to Signal Processing, Ph.D. Dissertation, NCSU, Math. Dept., 1987. |
| [21] | C.-T. Pan,A vector majorization method for solving a nonlinear programming problem, Lin. Alg. Appl., 1989, 119, 129–139. · Zbl 0676.65015 · doi:10.1016/0024-3795(89)90073-6 |
| [22] | C.-T. Pan and R. J. Plemmons,Parallel least squares modification using inverse factorizations, J. Comp. Appl. Math. 1989, 27, 109–127. · Zbl 0677.65037 · doi:10.1016/0377-0427(89)90363-4 |
| [23] | C.-T. Pan and K. Sigmon,A sharp bound for products of hyperbolic plane rotations, SIAM. Matrix Analysis, 1988, 9, 587–593. · Zbl 0689.15008 · doi:10.1137/0609049 |
| [24] | C. C. Paige,Error analysis of some techniques for updating orthogonal decompositions, Math. Comp., 1980, 34, 465–471. · Zbl 0422.65027 · doi:10.1090/S0025-5718-1980-0559196-9 |
| [25] | M. A. Saunders (1972),Large-scale linear programming using the Cholesky factorization, Stanford Univ. Report, STAN-CS-72-252, 1972. |
| [26] | G. W. Stewart,The effects of rounding erorr on an algorithm for downdating a Cholesky factorization, J. Inst. Math. Appl., 1979, 23, 203–213. · Zbl 0405.65019 · doi:10.1093/imamat/23.2.203 |
| [27] | D. R. Sweet,Fast Toeplitz orthogonalization, Numer. Math. 1984, 43, 1–21. · Zbl 0504.65017 · doi:10.1007/BF01389635 |
| [28] | J. H. Wilkinson,The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. · Zbl 0258.65037 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
