A Look-Ahead Levinson Algorithm for General
Tony Fan-Cheong Chan, Per Christian Hansen · 1992
A variety of are available for efficient numerical solution of Toeplitz systems: classical fast algo- rithms, such as those due to Levinson, Trench, and Bareiss, as well as the more recent asymptotically superfast algo- rithms due to de Hoog, Ammar and Gragg, and others. For the special class of symmetric positive definite Toeplitz matri- ces, the classical fast algorithms are known to be weakly numerically stable, but otherwise all these methods are poten- tially numerically unstable. General Toeplitz systems do occur frequently in many signal processing applications, and there is a need for which are numerically stable and can ex- ploit the Toeplitz structure. In this paper we present an extension of Levinson's algo- rithm that is guaranteed to be weakly stable for a large class of general Toeplitz matrices, namely, those that do not have many consecutive ill-conditioned leading principal submatrices. The new algorithm adapts itself to the given Toeplitz matrix by skipping over all the ill-conditioned leading principal subma- trices encountered during the solution process. This is done by a look-ahead strategy that monitors the condition of the leading principal submatrices and, if necessary, switches to a block step of suitable size. The overhead of the look-ahead algorithm is typically small compared to the classical Levinson algorithm, and in addition a reliable condition number estimate is produced.