Another class of Toeplitz solvers arises from Szego 's theory of
polynomials that are orthogonal with respect to a measure on the unit
circle in the complex plane.
A bounded nondecreasing distribution function 
with more than n points of increase
on 
defines a measure on the unit circle on the complex plane,
and an inner
product 
on the set 
of polynomials
of degree at most n, according to
This inner product on 
is determined
by its moments 
, 
.
Note that
so that the 
moment
depends only on the difference j-k. The moment matrix
is therefore
a Hermitian positive definite Toeplitz matrix.
Conversely, it follows from the solution of the classical
trigonometric moment problem that
every positive definite Hermitian Toeplitz matrix 
arises as the first n+1 moments of an inner product on the unit circle in
this manner. See, for example, [1,25].
The unique family of monic polynomials
that satisfy
with 
is said to be orthogonal with
respect to a measure on the unit circle.
These orthogonal polynomials were studied by Szego [36]
and are also known as the
monic Szego polynomials associated with 
.
Szego showed that these polynomials satisfy a simple recurrence
relation, from which it follows that they
can be generated using the following recursive procedure, which we
refer
to as the Szego recursions.
where
denotes the polynomial obtained by conjugating and reversing the
coefficients of 
in the monomial basis of
.
The coefficients of the monic Szego polynomials provide
a factorization of the inverse of the Toeplitz
matrix.
In particular, let 
denote the
unit right triangular matrix of order n+1 whose kth column contains
the coefficients of
, with 
and 
for j>k,
. Then in terms of matrices, the orthogonality
condition (4.2)
becomes
or equivalently,
where 
.
Thus, the coefficients of the Szego polynomials determine
the reverse Cholesky factorization
of 
, and moreover, the Szego recursions provide an 
algorithm for constructing this factorization.
This algorithm is known as the Levinson-Durbin algorithm.
See, for example, [10,24].
The Cholesky factorization (3.1) and inverse Cholesky
factorization (4.4) of M
are related by 
, so that there is a close connection
between Schur's algorithm and the Levinson-Durbin algorithm.
In fact, when 
is defined from 
as in Proposition 3.1,
then the Schur parameters generated by Schur's algorithm
are equal to the recurrence coefficients
generated during the Szego recursions.
These parameters
are often of interest in applications, where they
are known as reflection coefficients or partial correlation
coefficients.
This gives rise to the possibility of a hybrid algorithm, in which
the Szego polynomials are generated by the Szego recursions,
using recurrence coefficients 
generated by
Schur's algorithm.
Such an algorithm for computing
Szego polynomials is proposed in [20] because of its advantages
in parallel computing.
Moreover,
Schur's algorithm has better numerical behavior than Levinson's
algorithm [21,11], so
one can expect the hybrid approach to produce more
accurate Szego polynomial coefficients than the Levinson-Durbin
algorithm [21].
