Recently, a uniform approach was given 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 we study 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 ${\cal 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 superfast complexity ${\cal 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, our methods result in fast (and superfast), reliable algorithms for the inversion of striped Hankel, layered Hankel and (rectangular) block-Hankel matrices.