ISSN:
1572-9125
Keywords:
Padé approximation
;
row recurrence
;
fast algorithm
;
sawtooth recurrence
;
look-ahead
;
Toeplitz matrix
;
Levinson algorithm
;
Schur algorithm
;
biorthogonal polynomials
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A new look-ahead algorithm for recursively computing Padé approximants is introduced. It generates a subsequence of the Padé approximants on two adjacent rows (defined by fixed numerator degree) of the Padé table. Its two basic versions reduce to the classical Levinson and Schur algorithms if no look-ahead is required. The new algorithm can be viewed as a combination of the look-ahead sawtooth and the look-ahead Levinson and Schur algorithms that we proposed before, but now the look-ahead step size is minimal (as in the sawtooth version) and the computational costs are as low as in the least expensive competing algorithms (including our look-ahead Levinson and Schur algorithms). The underlying recurrences link well-conditioned basic pairs,i.e., pairs of sufficiently different neighboring Padé forms. The algorithm can be used to solve Toeplitz systems of equationsTx = b. In this application it comes in several versions: anO(N 2) Levinson-type form, anO(N 2) Schur-type form, and a superfastO(N log2 N) Schur-type version. As an option of the first two versions, the corresponding block LDU decompositions ofT −1 orT, respectively, can be found.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01731983
Permalink
