an algorithm to compute generalized
Pade-Hermite forms
Harm Derksen
Abstract
An algorithm is given to compute the Pade-Hermite form for a
vector of power series. The complexity of computing Pade-Hermite
forms of type ( 1 2 n) is ( ( 1 + 2 +
d ; d ; : : :; d O n d d + n)2 ) which is
::: d
the same as other fast algorithms. The advantage of this algorithm is
that it also treats non-normal cases without any loss of speed. The
algorithm also can be used to nd a ( )-linear between a sequence of
k z
power series in . A very similar algorithm is found by Beckermann
z
and Labahn independently (cf. [1, 2]).
1 Introduction
Suppose that f (z ) 2 k[[z ]] is a formal power series with coecients in the
eld k. The pair (P (z ); Q(z )), where P and Q are polynomials in z whose
degrees are bounded by m and n respectively, is called Pade approximant
of f if
Q(z)f (z) = P (z) + O(z m+n+1 )
This means that P (z )=Q(z ) is a good approximation for f (z ). This
de nition is a special case of the de nition of the Pade-Hermite approx-
imant. Suppose f1 (z ); f2(z ); : : :; fn (z ) 2 k[[z ]] are all power series. A
vector (P1 (z ); P2(z ); : : :; Pn (z )) is called Pade-Hermite approximant of type
(d1; d2; : : :; dn) for (f1 ; f2; : : :; fn ) if
P1(z)f1 (z) + P2(z)f2(z) + : : : + Pn(z)fn (z) = O(z d1 +d2 +:::+d +n 1 ) (1)
n
and deg(Pi (z )) di for all i. If we take n = 2 and f2 (z ) = 1 then (P1 ; P2) is
exactly the Pade-approximant of type (d1; d2) for the power seriesPf1 (z ). To
compute P1 ; P2; : : :; Pn one could proceed as follows: Write Pi = dj =0 ai;j z j
i
for all i. Equation (1) de nes d1 + d2 + : : : + dn + n 1 homogeneous linear
1
equations in the variables ai;j (1 i n, 0 j di ). Because there are
d1 + d2 + : : : + dn + n variables there is a non-zero solution. Solving the system
of linear equations costs O((d1 + d2 + : : : + dn )3) operations (multiplication,
subtraction, etc.) in the eld k. This can be done better.
Della Dora and Dicrescenzo gave in [6] an ecient algorithm to com-
pute these Pade-Hermite approximants using Pade-Hermite tables. Further
Paszkowski gave in [8] another ecient algorithm. Unfortunately these al-
gorithms work only in the case that (f1 ; f2; : : :; fn ) is normal. Roughly
speaking this means that (1) has for every type (d1 ; d2; : : :; dn) only one so-
lution (P1 ; P2; : : :; Pn) up to scalar multiplication with elements of the eld
k. In [4] Cabay and Labahn present an algorithm which also works in the
non-normal case. But in the non-normal case the complexity might be worse
than O(n(d1 + d2 + : : : + dn )2 ). In this paper an algorithm is presented which
reaches O(n(d1 + d2 + : : : + dn )2) in the normal as well in the non-normal
case.
2 De nitions and preliminaries
De nition 1 A polynomial vector (P1; P2; : : :; Pn) 2 k[z]n is called a Pade-
Hermite form of type (d1; d2; : : :; dn ) for the vector (f1; f2 ; : : :; fn ) 2 k[[z ]]n
of formal power series if
1. deg(Pi ) di for all i = 1; 2; : : :; n.
P
2. ni=1 Pi fi = O(z d1 +d2 +:::+d +n 1 )
n
3. Pi 6= 0 for some i.
Theorem 2 For every power series vector (f1; f2; : : :; fn) and every se-
quence d1 ; d2; : : :; dn of non-negative integers, there exists a Pade-Hermite
form of type (d1; d2; : : :; dn) for (f1 ; f2; : : :; fn ) 2 k[[z ]]n.
PProof: Represent the coecients of Pi by indeterminates, say Pi =
d a z j for all i. The second condition yields d + d + : : : + d + n 1
j =0
i
i;j 1 2 n
linear equations, but there are d1 + d2 + : : : + dn + n indeterminates. Hence
there is a non-zero solution for the ai;j . 2
If P~ = (P1; : : :; Pn ) is a polynomial
P vector, and f~ = (f1; : : :; fn ) is a vector
of power
P series, then the inproduct i=1 Pi fi 2 k[[z ]] is denoted by hP~ ; f~i. If
n
1
g = i=0 gizi 2 k[[z]] is a power series, then the valuation of g is de ned by
2
v (g ) = minfi j gi 6= 0g. If g = 0 then v (g ) = 1. For any polynomial vector
P~ = (P1 ; : : :; Pn ) 2 k[z]n we de ne deg(P~ ) = max(deg(P1 ); : : :; deg(Pn )).
We will say that P~ is of type i, if deg(Pi ) = deg(P~ ) and deg(Pj ) < deg(P~ )
for all j > i. This will be denoted by type(P~ ) = i. If P~ and Q~ are two
polynomial vectors, then we will say that P~ is smaller than Q~ (P~ < Q~ ) if
deg(P~ ) < deg(Q~ ) or deg(P~ ) = deg(Q~ ) and type(P~ ) < type(Q~ ).
Theorem 3 Properties of type and deg:
1. if P~ and Q~ are polynomial vectors, then type(P~ + Q~ ) 2
ftype(P~ ); type(Q~ )g
2. if type(P~ ) = type(Q~ ) and P~ > Q~ then there exists a polynomial q 2
k[z] such that P~ q Q~ < P~
3. if Q~ < P~ then deg(P~ + Q~ ) = deg(P~ ) and type(P~ + Q~ ) = type(P~ )
The proof is left to the reader.
De nition 4 Let V k[z]n be a free sub-module of rank n. A sequence of
polynomial vectors Q~ 1; Q~ 2; : : :; Q~ n 2 V is called minimal vector sequence for
V if Q~ i is a non-trivial polynomial vector with minimal degree of type i for
i = 1; 2; : : :; n.
Observe that any free sub-module V k[z ]n of rank n has such a minimal
vector sequence.
Theorem 5 If V; Q~ 1; : : :; Q~ n are as in the previous de nition, then V is
generated by Q~ 1 ; : : :; Q~ n as a k[z ]-module.
Proof: De ne W = k[z ]Q~ 1 + k[z ]Q~ 2 + : : : + k[z ]Q~ n V . Suppose V 6= W .
Let P~ be a polynomial vector in V n W which is minimal (with respect to the
ordering on polynomial vectors). Let i = type(P~ ). There exists a polynomial
q 2 k[z] such that P~ q Q~ i < P~ (see theorem 3, property 2). Because of
the minimality of P~ we get P~ q Q~ i 2 W , hence P~ 2 W . Contradiction, so
V = W. 2
Now we x a power series vector f~ = (f1 ; : : :; fn ) 2 k[z ]n and we x a free
sub-k[z ]-module V k[z ]n of rank n. For every j we de ne a sub-module
of V by
~ f~i) j g
Vj = fP~ 2 V j v (hP;
3
Of course V Vj z j V , therefore Vj is a free sub-module of V of rank
n. Suppose that Q~ 1; : : :; Q~ n is a minimal vector sequence for Vj . How to
construct a minimal vector sequence for Vj +1 ? This can be done as follows:
If v (hQ~ i; f~i) j + 1 for all i, then Vj = Vj +1 and we are done. Otherwise
choose an i such that
(a) v (hQ~ i; f~i) = j
(b) if v (hQ~ l; f~i) = j for some l 6= i, then Q~ i < Q~ l
Suppose that v (hQ~ l; f~i) = j for some l. We can choose now some 2 k such
that v (hQ~ l Q~ i ; f~i) = v (hQ~ l; f~i hQ~ i; f~i) > j . Replace Q~ l by Q~ l Q~ i .
The degree and type of Q~ l doesn't change (see theorem 3, property 3). So
Q~ 1 ; : : :; Q~ n remains a minimal vector sequence. After some wiping, we may
assume that v (hQ~ i; f~i) = j and v (hQ~ l; f~i) > j for l 6= i. We will prove that
Q~ 1 ; : : :; Q~ i 1; z Q~ i; Q~ i+1 ; : : :; Q~ n is a minimal vector sequence. If P~ 2 Vj+1
has type l 6= i, thenPP~ 2 Vi, hence deg(P~ ) deg(Q~ l ). Suppose P~ 2 Vj +1 has
type i. Write P~ = nl=1 al Q~ l . If ai = 0 then the type of P~ cannot be i (see
theorem 3, property 1). If ai 6= 0, then v (ai) > 0 because v (hP; ~ f~i) j + 1.
Hence the degree of ai is at least 1. So deg(P~ ) deg(ai ) deg(Q~ i) deg(z Q~ i ).
Let d be xed non-negative integer. A Pade-Hermite form of type
(d; d; d; : : :; d) for f~ is a polynomial vector P~ 2 Vnd+n 1 such that deg(P~ )
d. We know that such a P~ exists (see theorem 2). Assume that Q~ 1 ; : : :; Q~ n
is a minimal vector sequence of Vnd+n 1 and choose an l such that deg(Q~ l) is
minimal. Let i = type(P~ ). Now deg(Q~ l ) deg(Q~ i ) deg(P~ ) d. There-
fore Q~ l is also a Pade-Hermite form of type (d; d; d; : : :; d) for f~. This gives
us the following algorithm:
3 An algorithm to compute a Pade-Hermite form
of type ( ) d; d; d; : : : ; d
The algorithm below computes for a given vector f~ of formal power series
in z the Pade-Hermite form of type (d; d; d; : : :; d). In the algorithm \coe "
stands for a procedure such that for any power series f 2 k[[z ]] and any
integer j the output of coe (f; j ) is the coecient of z j .
4
input: f~ = (f1; f2 ; : : :; fn ), d
for k from 1 to n do
Q~ k := (0; 0; : : :; 0; 1; 0; : : :; 0) (n-dimensional vector with 1 as k-th entry)
for j from 0 to nd + n 2 do
i := 0
for k from 1 to n do
if v (hQ~ i; f~i) = j and (Q~ k < Q~ i or i = 0) then i := k
if i 6= 0 then
:= coe (hQ~ i; f~i; j )
Q~ i := 1 Q~ i
for k from 1 to n do
if k 6= i then
:= coe (hQ~ k ; f~i; j )
Q~ k := Q~ k Q~ i
Q~ i := z Q~ i
p := 1
for k from 2 to n do
if deg(Q~ k ) < deg(Q~ p ) then p := k
output: Q~ p
4 Finding relations with polynomial coecients
~ f~i = 0 for
Suppose that f1 ; : : :; fn are dependent over k(z ), let's say hP;
~
some P 2 k[z ] . The described algorithm is also very useful for nding a
n
relation. De ne for every j a nite dimensional vector space Wj Vj by
Wj = fQ~ 2 V j v (hQ;
~ f~i) j ^ deg(Q~ ) deg(P~ )g
T
Further de ne W1 = 1 j =0 Wj . Now W1 contains all relations of f~ of degree
deg(P~ ), so all Q~ 2 k[z]n satisfying hQ;
~ f~i = 0 and deg(Q~ ) deg(P~ ). We
have an in nite descending chain of nite dimensional vector spaces:
W0 W1 W2 : : :
So there must be an positive integer N such that W1 = WN = WN +1 =
WN +2 = : : :. If we take d such that dn + n 1 N , then the output of the
algorithm will be a k(z )-linear relation between f1 ; f2 ; : : :; fn .
5
5 Pade-Hermite forms of arbitrary type
In order to compute Pade-Hermite forms of arbitrary type we make the fol-
lowing de nitions: If d = (d1; d2; : : :; dn) is a vector of non-negative integers
and P~ = (P1; P2; : : :; Pn ) 2 k[z ]n is a polynomial vector then
degd (P~ ) = maxfdeg(P1 ) d1 ; deg(P2) d2 ; : : :; deg(Pn ) dn g
and typed (P~ ) = minfi j deg(Pi ) di = degd (P )g
If we replace deg by degd and type by typed in the algorithm of section 3
then the output will be a Pade- form for f~ of type (d1; d2; : : :; dn).
References
[1] B. Beckermann, G. Labahn, A uniform approach for Hermite Pade
Approximants and their Matrix-type generalizations, Manuscript.
[2] B. Beckermann, G. Labahn, A uniform approach for the fast compu-
tation of Matrix-type Pade approximants, Manuscript.
[3] S. Cabay and D. K. Choi, Algebraic computations of scaled pade frac-
tions, Siam J. Comput., Vol. 15, No. 1, pp. 243-270, February 1986.
[4] S. Cabay and G. Labahn, A Fast, Reliable Algorithm for Calculating
Pade-Hermite Forms, Proceedings of the ACM-SIGSAM 1989, Inter-
national Symposium on Symbolic and Algebraic Computations, ACM
Press, 1989.
[5] S. Cabay and G. Labahn, Matrix Pade fractions and their computa-
tion, Siam J. Comput., Vol 19, No. 4, pp. 639-657, August 1989.
[6] J. Della Dora and C. Dicrescenzo, Approximants de Pade-Hermite,
Numer. Math, 43, pp. 23-57, 1984.
[7] H. Pade, Sur la Representation Approchee d'une Fonction par des
Fractions Rationelles, Ann Ecole Nor., pp 1-93, supplement Thesis,
1892.
[8] S. Paszkowski, Recurrence Relations in Pade-Hermite Approximation,
J. of Comp. and Appl. Math, 19, pp. 99-107, 1987.
