tire present a fraction-free approach to the computation of matrix Pad& systems.The method relies on determining a modified Schur complement for the coefficient matrices of the linear systems of equations that are associated to matrix Pad& approximation problems.By using this modified Schur complement for these matrices we are able to obtain a fast hybrid fraction-free algorithm for their computation.The algorithm is genera] and requires no extra assumptions on its input.

In a recent paper, Cabay, Jones, and Labahn develop a fast, iterative, lookahead algorithm for numerically computing Pade ´-Hermite systems and simultaneous Pade ´systems along a diagonal of the associated Pade ´tables.Included in their work is a detailed error analysis showing that the algorithm is weakly stable.In this article, we describe a Fortran implementation, VECTOR_PADE, of this algorithm together with a number of numerical experiments.These experiments show that the theoretical error bounds obtained by Cabay, Jones, and Labahn reflect the general behavior of the actual error, but that in practice these bounds are large overestimates.

A set of new formulae for the inverse of a block Hankel (or block Toeplitz) matrix is given. The formulae are expressed in terms of certain matrix Padé forms, which approximate a matrix power series associated with the block Hankel matrix. By using Frobenius-type identities between certain matrix Padé forms, the inversion formulae are shown to generalize the formulae of Gohberg–Heinig and, in the scalar case, the formulae of Gohberg–Semencul and Gohberg–Krupnik. The new formulae have the significant advantage of requiring only that the block Hankel matrix itself be nonsingular. The other formulae require, in addition, that certain submatrices be nonsingular. Since effective algorithms for computing the required matrix Padé forms are available, the formulae are practical. Indeed, some of the algorithms allow for the efficient calculation of the inverse not only of the given block Hankel matrix, but also of any nonsingular block principal minor.

We present a new fast algorithm for the calculation of a Padé-Hermite form for a vector of power series. When the vector of power series is normal, the algorithm is shown to calculate a Padé-Hermite form of type (n0, ··· , nk) in O(k·(n02 + ··· + nk2)) operations. This complexity is the same as that of other fast algorithms for computing Padé-Hermite approximants. However, unlike other algorithms, the new algorithm also succeeds in the non-normal case, usually with only a moderate increase in cost.

For matrix power series with coefficients over a field, the notion of a matrix power series remainder sequence and its corresponding cofactor sequence are introduced and developed. An algorithm for constructing these sequences is presented. It is shown that the cofactor sequence yields directly a sequence of Pade fractions for a matrix power series represented as a quotient $B(z)^{ - 1} A(z)$. When $B(z)^{ - 1} A(z)$ is normal, the complexity of the algorithm for computing a Pade fraction of type $(m,n)$ is $O(p^3 (m + n)^2 )$, where p is the order of the matrices $A(z)$ and $B(z)$. For a power series that are abnormal for a given $(m,n)$, Padé fractions may not exist. However, it is shown that a generalized notion of Padé fraction, the Padé form, which is introduced in this paper, does always exist and can be computed by the algorithm. In the abnormal case, the algorithm can reach a complexity of $O(p^3 (m + n)^3 )$, depending on the nature of the abnormalities. In the special case of a scalar power series, however, the algorithm complexity is $O(m + n)^2 $, even in the abnormal case.

An algorithm for computing the power series solution of a system of linear equations with components that are dense univariate polynomials over a field is described and analyzed. A method for converting the power series solution to rational form is derived. Theoretical and experimental cost estimates are obtained and used to identify classes of problems for which the power series method outperforms modular methods. Finally, it is shown that the power series method also provides an effective mechanism for solving the problem in which the coefficients of the polynomials are from the ring of integers.

Two companion algorithms are developed for constructing Pade fractions along an off-diagonal path of the Padé table for a function ${{ - A(z)} / {B(z)}}$, where $A(z)$ and $B(z)$ are formal power series over a field. One of the algorithms computes the first n Padé fractions along the off-diagonal in time $O(n^2 )$. When $A(z)$ and $B(z)$ are finite power series (i.e., polynomials), it is shown that the algorithm is equivalent to Euclid’s extended algorithm for computing greatest common divisors. The other algorithm, a generalization of the first, proceeds along the off-diagonal in quadratic steps, and is of complexity $O(n\log ^2 n)$. When $A(z)$ and $B(z)$ are polynomials, the second algorithm becomes a fast Euclid’s extended algorithm for computing greatest common divisors. The algorithm is of the same complexity as other fast greatest common divisor methods, but its iterative nature provides a practical advantage during implementation. The algorithms may also be used for computing Padé fractions along an anti-diagonal path of the Padé table. The fast algorithm is of the same complexity as other fast algorithms for anti-diagonal computations. However, it has the advantage of being able to determine easily any specific Padé fraction along the anti-diagonal.