Problems related to solving the system of equations **Mx=b**,
where

is a Hermitian positive definite Toeplitz matrix,
arise in several fundamental problems of signal processing, time
series analysis, and image processing.
There has therefore been a significant amount of effort devoted
to developing efficient
algorithms for solving positive definite Toeplitz equations.
We refer to any of these algorithms as a * Toeplitz solver*.

The development of Toeplitz solvers goes back to the work
of Levinson [33] in 1947, who presented a fast algorithm
for solving a positive definite Toeplitz system of equations
for solving discrete-time Wiener filtering problems. This work
and subsequent work by
Durbin [17] for solving the Yule-Walker equations of
prediction theory, Trench [37] for constructing from the
solution of one set of Yule-Walker equations, and Bareiss
[8] for
computing a triangular factorization of **M** form the foundation
for direct algorithms for Toeplitz equations.

Toeplitz solvers can be divided into two classes: direct methods
and iterative methods. The direct methods are further classified
according to their arithmetic complexity. We will say that
an algorithm that requires floating-point arithmetic
operations (flops) is a * fast* algorithm. This is in contrast
with the flops required by algorithms for arbitrary positive
definite matrices, such as Cholesky's method. We will also refer to
a method that requires flops as a *
superfast* algorithm. While any superfast algorithm will require fewer
flops than a fast algorithm for sufficiently large **n**, the practical
value of a superfast algorithm will depend on when this *
crossover* of flop counts is achieved, and also on the tractability
of implementing the algorithm on a computer.

In this paper we give an overview of several direct Toeplitz solvers and their connections with Schur functions and Szego polynomials. Although knowledge of the connections with the classical theory is not necessary to derive the algorithms, we find the connections illuminating on the overall mathematical structure of the problems being considered. In fact, we have found the classical connections invaluable in understanding and implementing the superfast Toeplitz solver described in [5,6].

Thu Sep 18 20:40:30 CDT 1997