On the Stability of the Bareiss and Related Toeplitz Factorization Algorithms
- 1 January 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 16 (1), 40-57
- https://doi.org/10.1137/S0895479891221563
Abstract
This paper contains a numerical stability analysis of factorization algorithms for computing the Cholesky decomposition of symmetric positive definite matrices of displacement rank 2. The algorithms in the class can be expressed as sequences of elementary downdating steps. The stability of the factorization algorithms follows directly from the numerical properties of algorithms for realizing elementary downdating operations. It is shown that the Bareiss algorithm for factorizing a symmetric positive definite Toeplitz matrix is in the class and hence the Bareiss algorithm is stable. Some numerical experiments that compare behavior of the Bareiss algorithm and the Levinson algorithm are presented. These experiments indicate that generally (when the reflection coefficients are not all of the same sign) the Levinson algorithm can give much larger residuals than the Bareiss algorithm. This paper contains a numerical stability analysis of factorization algorithms for computing the Cholesky decomposition of symmetric positive definite matrices of displacement rank 2. The algorithms in the class can be expressed as sequences of elementary downdating steps. The stability of the factorization algorithms follows directly from the numerical properties of algorithms for realizing elementary downdating operations. It is shown that the Bareiss algorithm for factorizing a symmetric positive definite Toeplitz matrix is in the class and hence the Bareiss algorithm is stable. Some numerical experiments that compare behavior of the Bareiss algorithm and the Levinson algorithm are presented. These experiments indicate that generally (when the reflection coefficients are not all of the same sign) the Levinson algorithm can give much larger residuals than the Bareiss algorithm.Keywords
This publication has 15 references indexed in Scilit:
- Optimization by Direct Search in Matrix ComputationsSIAM Journal on Matrix Analysis and Applications, 1993
- From Bareiss' algorithm to the stable computation of partial correlationsJournal of Computational and Applied Mathematics, 1989
- Stabilized hyperbolic Householder transformationsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1989
- Analysis of a recursive least squares hyperbolic rotation algorithm for signal processingLinear Algebra and its Applications, 1988
- A Note on Downdating the Cholesky FactorizationSIAM Journal on Scientific and Statistical Computing, 1987
- The weak and strong stability of algorithms in numerical linear algebraLinear Algebra and its Applications, 1987
- QR factorization of Toeplitz matricesNumerische Mathematik, 1986
- The Numerical Stability of the Levinson-Durbin Algorithm for Toeplitz Systems of EquationsSIAM Journal on Scientific and Statistical Computing, 1980
- Numerical solution of linear equations with Toeplitz and Vector Toeplitz matricesNumerische Mathematik, 1969
- Triangular factors of modified matricesNumerische Mathematik, 1965