A Look-Ahead Levinson Algorithm for Indefinite Toeplitz Systems
Tony Fan-Cheong Chan, Per Christian Hansen · SIAM Journal on Matrix Analysis and Applications · 1992
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.