LOOK-AHEAD LEVINSON- AND SCHUR-TYPE RECURRENCES IN THE PAD ET ABLE
Martin H. Gutknecht, Marlis Hochbruck · 1994
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 lookahead 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).