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 jth 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 nth 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.
