In 1969, Bareiss [8] presented an algorithm of complexity for computing a triangular factorization of a Toeplitz matrix. When applied to a positive definite Toeplitz matrix M = , Bareiss's algorithm computes the Cholesky factorization

where **L** is a unit lower triangular matrix,
and , with
each .

It is now well known that the algorithm of Bareiss applied to a positive definite Toeplitz matrix is a manifestation of Schur's algorithm. Algorithms related to Bareiss's algorithm are therefore also referred to as algorithms of `Schur type'. See [28,31] for discussions of this connection as well as wider connections of Schur's algorithm with signal processing and matrix computation. The explicit relationship between Schur's algorithm and Cholesky factorization is given in the following proposition [5].

Thus,
the **j**th column of the Cholesky factor **L**
is determined directly from
the first **n-j**
coefficients of the denominator polynomial
of each function generated by Schur's algorithm.

The computations involved in Schur's algorithm can be viewed in terms of infinitely long column vectors containing the coefficients of and . The Schur parameter determines a scaled hyperbolic transformation that produces a zero in the first entry of the second column. Then the second column is shifted up, or equivalently, the first column is shifted down, corresponding to dividing the numerator by .

Of course, in practice only finitely many of the coefficients
and will be used. Note that
the first **n** coefficients of and will determine
the first **n-k** coefficients of and () and the first **n** Schur parameters
. One can arrange the computation of these coefficients to
proceed `column-by-column', each step producing vectors of length one
less than the previous column.
We refer to this arrangement
as the * parallel form*
of Schur's algorithm, since parallel implementations of Schur's
algorithm will produce one set of columns from the previous set
in one time step. This it is the natural form for the algorithm
from the perspective of * displacement structure* (see
[31]).

Alternately, the computations can be arranged so that each
pair of
coefficients of the initial power series
is entered and processed sequentially. This results in the
* progressive form* of Schur's algorithm which, in terms of the
infinite column vectors above, can be thought of as
a rowwise arrangement of Schur's algorithm. This form is more natural
from the point of
view of continued fractions, since the number of coefficients in the
initial numerator and denominator need not be known in advance.
In fact, having generated the **n**th row of **LD**, and the first **n** Schur
parameters, one can naturally add the next row, and generate the next
Schur parameter.

The parallel and progressive forms of Schur's algorithm are simply rearrangements of each other. They compute the Schur parameters and the first coefficients of and , , using roughly multiplications and additions.

Thu Sep 18 20:40:30 CDT 1997