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 **k**th 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].

Thu Sep 18 20:40:30 CDT 1997