Volume 2, pp. 104-129, 1994.

Look-ahead Levinson- and Schur-type recurrences in the Padé table

Martin H. Gutknecht and Marlis Hochbruck

Abstract

For computing Padé approximants, we present presumably stable recursive algorithms that follow two adjacent rows of the Padé table and generalize the well-known classical Levinson and Schur recurrences to the case of a nonnormal Padé table. Singular blocks in the table are crossed by look-ahead steps. Ill-conditioned Padé approximants are skipped also. If the size of these look-ahead steps is bounded, the recursive computation of an $(m,n)$ Padé approximant with either the look-ahead Levinson or the look-ahead Schur algorithm requires $O(n^2)$ operations. With recursive doubling and fast polynomial multiplication, the cost of the look-ahead Schur algorithm can be reduced to $O(n{\log }^{2}n)$.

Full Text (PDF) [311 KB], BibTeX

Key words

Padé approximation, Toeplitz matrix, Levinson algorithm, Schur algorithm, look-ahead, fast algorithm, biorthogonal polynomials, Szegő polynomials.

AMS subject classifications

41A21, 42A70, 15A06, 30E05, 60G25, 65F05, 65F30.