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 .

Thu Sep 18 20:40:30 CDT 1997