A LOOK-AHEAD LEVINSON ALGORITHM FOR GENERAL TOEPLITZ-SYSTEMS

A variety of algorithms are available for efficient numerical solution of Toeplitz systems: classical "fast algorithms," such as those due to Levinson, Trench, and Bareiss, as well as the more recent "asymptotically superfast algorithms" due to de Hoog, Ammar and Gragg, and others. For the special class of symmetric positive definite Toeplitz matrices, the classical "fast algorithms" are known to be weakly numerically stable, but otherwise all these methods are potentially numerically unstable. General Toeplitz systems do occur frequently in many signal processing applications, and there is a need for algorithms which are numerically stable and can exploit the Toeplitz structure. In this paper we 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.