A look-ahead Levinson algorithm for general Toeplitz systems

摘要

The authors present an extension of Levinson's algorithm 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 submatrices 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.