next up previous
Next: Schur polynomials. Up: Classical Foundations of Algorithms Previous: Toeplitz Inversion Formulas

The Generalized Schur Algorithm

  Direct algorithms of arithmetic complexity for performing Phase 1 of a Toeplitz solver have been presented in [14,9,15,34,5,6]. These algorithms all rely on Toeplitz inversion formulas for their second phase, and use doubling procedures and fast Fourier transform techniques to perform the first phase. We refer to these as algorithms superfast Toeplitz solvers. However, these algorithms will involve fewer arithmetic operations than a fast algorithm only for sufficiently large n. It is shown in [5] that the superfast Toeplitz solver presented independently by Musicus [34] and de Hoog [15] can be interpreted in terms of a doubling strategy applied to the continued fraction generated by Schur's algorithm. This algorithm can be viewed as a hybrid algorithm that uses the results of a fast implementation of Schur's algorithm to construct the Szego polynomial .

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