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].