next up previous
Next: The Szego Recursions Up: Classical Foundations of Algorithms Previous: Schur's Algorithm and

Fast Cholesky factorization

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.



next up previous
Next: The Szego Recursions Up: Classical Foundations of Algorithms Previous: Schur's Algorithm and



Greg Ammar
Thu Sep 18 20:40:30 CDT 1997