next up previous
Next: References Up: The Generalized Schur Previous: Schur polynomials.

The Generalized Schur Algorithm

We can now describe the doubling generalization of Schur's algorithm, which forms the basis for the first phase of our superfast Toeplitz solver.

Recall that if we perform m steps of Schur's algorithm on the Schur function , we can obtain the mth Schur polynomials and . Moreover, these polynomials are determined by the first m coefficients of and . Let and denote the polynomials of degree less than m formed from these coefficients. To describe the doubling procedure, we assume that and have been computed from and , and we seek to compute and from and .

Having obtained and , the mth Schur function is given by

It can be shown [5] that

 

so that the first m terms of the numerator and denominator of can be taken from

 

We can now perform the doubling step: Since is also a Schur function, we can use the same procedure that computed and from and to compute the Schur polynomials and that result from m steps of Schur's algorithm applied to and .

Let denote the LFT that results from m steps of Schur's algorithm applied to . Then we have , so that . Writing this composition in terms of Schur polynomials, we obtain

 

This discussion is summarized by the following recursive description of the doubling procedure.

 

The algorithm can be started by performing Step 0 directly by, for example, setting and . More generally, we can use Schur's algorithm to generate for a small value of , and obtain , from the Schur parameters and the recursions (6.1).

Thus, the generalized Schur algorithm consists of various polynomial multiplications and additions performed in a recursive manner. The multiplication of polynomials can be efficiently performed using standard FFT techniques. This results in an algorithm for computing and , where . The Toeplitz system of equations can then be solved by forming from , by Proposition 6.1, and using a Toeplitz inversion formula to perform the solution phase of the algorithm in arithmetic operations.

A detailed analysis of the implementation for Hermitian Toeplitz matrices is given in [4]. Further refinements for real Toeplitz matrices are described in [6], where it is shown in that the first phase of the superfast Toeplitz solver can be implemented using fewer than real arithmetic operations for a real Toeplitz matrix , where . Since the Levinson-Durbin algorithm requires more than operations, the superfast algorithm has a smaller operation count for . Experimental results presented in [7] confirm that the two procedures require approximately the same execution time for n=256, and that the relative efficiency of the superfast algorithm quickly increases for larger values of . Moreover, experimental results indicate that there is little or no degradation in the accuracy of the superfast algorithm compared to the Levinson-Durbin algorithm [4,7].

While the experimental results indicate that this superfast algorithm may be as reliable as the Levinson-Durbin algorithm for the first phase of a Toeplitz solver, no stability analysis along the lines of [21] or [11] has yet been performed. However, since the Schur polynomials are generalizations of the Schur parameters, the superfast algorithm is closely related to the hybrid algorithm mentioned at the end of Section 4. This is encouraging in that the superfast algorithm may behave more like the hybrid algorithm than the Levinson-Durbin algorithm.



next up previous
Next: References Up: The Generalized Schur Previous: Schur polynomials.



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