A Look-Ahead Levinson Algorithm for General Toeplitz Systems

Tony F. Chan*, Per C. Hansen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1079-1090
Number of pages12
JournalIEEE Transactions on Signal Processing
Volume40
Issue number5
DOIs
StatePublished - Jan 1 1992
Externally publishedYes

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A Look-Ahead Levinson Algorithm for General Toeplitz Systems'. Together they form a unique fingerprint.

Cite this