A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
- 1 July 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 15 (3), 804-823
- https://doi.org/10.1137/s0895479892230031
Abstract
Recently, a uniform approach was given by B. Beckermann and G. Labahn [Numer. Algorithms, 3 (1992), pp. 45–54] for different concepts of matrix-type Padé approximants, such as descriptions of vector and matrix Padé approximants along with generalizations of simultaneous and Hermite Padé approximants. The considerations in this paper are based on this generalized form of the classical scalar Hermite Padé approximation problem, power Hermite Padé approximation. In particular, this paper studies the problem of computing these new approximants. A recurrence relation is presented for the computation of a basis for the corresponding linear solution space of these approximants. This recurrence also provides bases for particular subproblems. This generalizes previous work by Van Barel and Bultheel and, in a more general form, by Beckermann. The computation of the bases has complexity $\mathcal{O} ( \sigma ^2 )$, where $\sigma $ is the order of the desired approximant and requires no conditions on the input data. A second algorithm using the same recurrence relation along with divide-and-conquer methods is also presented. When the coefficient field allows for fast polynomial multiplication, this second algorithm computes a basis in the super-fast complexity $\mathcal{O}( \sigma \log ^2 \sigma )$. In both cases the algorithms are reliable in exact arithmetic. That is, they never break down, and the complexity depends neither on any normality assumptions nor on the singular structure of the corresponding solution table. As a further application, these methods result in fast (and superfast) reliable algorithms for the inversion of striped Hankel, layered Hankel, and (rectangular) block-Hankel matrices.
Keywords
This publication has 20 references indexed in Scilit:
- A Weakly Stable Algorithm for Padé Approximants and the Inversion of Hankel MatricesSIAM Journal on Matrix Analysis and Applications, 1993
- A uniform approach for Hermite Padé and simultaneous Padé approximants and their matrix-type generalizationsNumerical Algorithms, 1992
- A superfast algorithm for multi-dimensional Padé systemsNumerical Algorithms, 1992
- A reliable method for computing M-Padé approximants on arbitrary staircasesJournal of Computational and Applied Mathematics, 1992
- On the theory and computation of nonperfect padé-hermite approximantsJournal of Computational and Applied Mathematics, 1992
- The structure of the singular solution table of the M-Padé approximation problemJournal of Computational and Applied Mathematics, 1990
- Simultaneous partial Padé approximantsJournal of Computational and Applied Mathematics, 1988
- Algebraic Computations of Scaled Padé FractionsSIAM Journal on Computing, 1986
- Fast solution of toeplitz systems of equations and computation of Padé approximantsJournal of Algorithms, 1980
- The interruption phenomenon for generalized continued fractionsBulletin of the Australian Mathematical Society, 1978