A Look-Ahead Levinson Algorithm for Indefinite Toeplitz Systems
- 1 April 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 13 (2) , 490-506
- https://doi.org/10.1137/0613032
Abstract
An extension of Levinson’s algorithm for solving linear systems with symmetric indefinite Toeplitz matrices is presented. This new algorithm is able to “look ahead” and, if necessary, use block Gaussian elimination to skip all ill-conditioned leading principal submatrices encountered during the recursive processing. This makes the new algorithm numerically stable for a broader class of symmetric Toeplitz matrices than the standard Levinson algorithm. In addition, a reliable condition number estimate is produced. The overhead is typically small.Keywords
This publication has 13 references indexed in Scilit:
- A fast but unstable orthogonal triangularization technique for Toeplitz matricesLinear Algebra and its Applications, 1987
- The weak and strong stability of algorithms in numerical linear algebraLinear Algebra and its Applications, 1987
- Computing the Minimum Eigenvalue of a Symmetric Positive Definite Toeplitz MatrixSIAM Journal on Scientific and Statistical Computing, 1986
- A generalization of the Levinson algorithm for Hermitian Toeplitz matrices with any rank profileIEEE Transactions on Acoustics, Speech, and Signal Processing, 1985
- Stability of Methods for Solving Toeplitz Systems of EquationsSIAM Journal on Scientific and Statistical Computing, 1985
- Inversion of Toeplitz Matrices which are not Strongly Non-singularIMA Journal of Numerical Analysis, 1985
- An exact recursion for the composite nearest-neighbor degeneracy for a 2×N lattice spaceJournal of Mathematical Physics, 1984
- The Numerical Stability of the Levinson-Durbin Algorithm for Toeplitz Systems of EquationsSIAM Journal on Scientific and Statistical Computing, 1980
- Inverses of Toeplitz Operators, Innovations, and Orthogonal PolynomialsSIAM Review, 1978
- A view of three decades of linear filtering theoryIEEE Transactions on Information Theory, 1974