## 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^2n)$.

Full Text (PDF) [311 KB]

### 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.

< Back