The Lazy Hermite Reduction

Manuel Bronstein

INRIA, Sophia Antipolis

Algorithms Seminar

May 4, 1998

[summary by Grégoire Lecerf]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
The Hermite reduction is a symbolic integration technique that reduces algebraic functions to integrands having only simple affine poles [1, 2, 7]. While it is very effective in the case of simple radical extensions, its use in more general algebraic extensions requires the precomputation of an integral basis, which makes the reduction impractical for either multiple algebraic extensions or complicated ground fields. In this work, Manuel Bronstein shows that the Hermite reduction can be performed without a priori computation of either a primitive element or integral basis, computing the smallest order necessary for a particular integrand along the way.



1   Preliminaries

We recall in this section some terminology and results from [2, 4, 6] that will be needed in the main algorithm. Let R be an integral domain, K its quotient field and E a finitely generated algebraic extension of K. An element aÎ E is called integral over R if there is a monic polynomial pÎ R[X] such that p(a)=0. The set
OR={aÎ E such that a is integral over R}
is called the integral closure of R in E. It is a ring and a finitely generated R-module. A basis of E over K that generates OR over R is called an integral basis. Any submodule of OR is finitely generated over R.

Let now k be a differential field of characteristic 0 with derivation '. An element t in a differential extension of k is called a monomial over k if t is transcendental over k and t' Î k[t], which implies that both k[t] and k(t) are closed under differentiation. We say that pÎ k[t] is normal (with respect to ') if gcd(p,p')=1, and special (with respect to ') if gcd(p,p')=p. Factors and products of specials are special, and factors and least common multiples of normals are normal. Note that normal polynomials are squarefree. Conversely, for pÎ k[t] squarefree, let ps=gcd(p,p') and pn=p/ps. Then, ps is special and pn is normal.

2   Extending a Module

Let R be a Euclidean domain, K its quotient field, V a finite-dimensional vector space over K with basis (w1,...,wn) and Mw=Rw1+...+Rwn the module generated by (w1,...,wn). Let w Î V and M = Rw+Mw be the module generated by (w,w1,...,wn). We describe in this section an algorithm for computing a generating set (m1,...,mn) of M over R.

Since (w1,...,wn) generates V over K, we can write
w=
1
d
(a1w1+...+anwn)
where d,a1,...,an Î R and d¹0. This implies that M is the submodule of R(1/d)w1+...+R(1/d)wn generated by w1,...,wn,w, i.e., by the rows of
M=
æ
ç
ç
ç
ç
ç
ç
è
d      
  d    
    ·  
 · 
  ·		  
      d
a1 a2 ... an
ö
÷
÷
÷
÷
÷
÷
ø
Using Hermitian row reduction, we can zero out the last row of M, obtaining a matrix of the form
N=
æ
ç
ç
ç
ç
ç
ç
ç
ç
è
b1,1 b1,2 ... b1,n
b2,1 b2,2 ... b2,n
·
·
·		 ·
·
·		   ·
·
·
bn,1 bn,2 ·  
 · 
  ·		 bn,n
0 0 ... 0
ö
÷
÷
÷
÷
÷
÷
÷
÷
ø
with bi,jÎ R. A generating set for M over R is then given by
mi=
1
d
n
å
j=1
bi,jwj  for   1£ i£ n.
The cost of this computation is O(n3) operations in k[t].

3   I-Bases

Let k be a differential field of characteristic 0 with derivation ', t a monomial over k, R=k[t], K=k(t), E a finitely generated algebraic extension of K and O the integral closure of R in E. Given any vector-space basis (w1,...,wn) of E over K, let fi,jÎ K be such that
wi'=
n
å
j=1
fi,jwj  for  1£ i£ n     (1)
and FwÎ R be the least common multiple of the denominators of all the fi,j's.
Definition 1   With the above notations, we say that (w1,...,wn) is an I-basis if Fw is normal and wiÎ O for each i.
For any vector-space basis of E over K we have an algorithm for transforming it into an I-basis within O(n3) operations in k(t).

4   The Lazy Reduction

With the notations as in the previous section, let (w1,...,wn) be an I-basis for E over K, the fi,j's be given by (1), Fw be the least common multiple of the denominators of all the fi,j's, and Mw be the n by n matrix with entry Fwfi,j at row i and column j. Let fÎ E and write
f=
A1w1+...+Anwn
D
where D,A1,...,AnÎ k[t] and gcd(A1,...,An,D)=1. Let D=d1d22··· dm+1m+1 be a squarefree factorization of D, di,s=gcd(di,di') and Ui=di/di,s for each i, S=d1,sd2,s2··· dm+1,sm+1, U=U1U22··· Umm and V=Um+1. Then,
D=SUVm+1
where S is special, V and all the squarefree factors of U are normal, and gcd(U,V)=1. Let Gw=Fw/gcd(Fw,UV). Note that Gw| Fw | GwUV. In addition, gcd(Gw,V)=1 by construction, and since the basis is an I-basis, Fw, and therefore Gw, are normal.

Consider the following linear system in k[t]/(V):
æ
ç
ç
è
GwUV
Fw
Mwt-mGwUV'In ö
÷
÷
ø
æ
ç
ç
ç
ç
ç
è
B1
B2
·
·
·
Bn
ö
÷
÷
÷
÷
÷
ø
=GwS-1
æ
ç
ç
ç
ç
ç
è
A1
A2
·
·
·
An
ö
÷
÷
÷
÷
÷
ø
    (2)
where Mwt is the transpose of Mw, In is the n by n identity matrix, and S-1 is the inverse of S modulo V. The classical Hermite reduction (where the wi's form an integral basis) proceeds by computing a solution of (2) in k[t]/(V) and using it to reduce the poles of the integrand. Even with an I-basis, any solution in k[t]/(V) does reduce the poles of the integrand.
Theorem 1   For any solution (B1,...,Bn) of (2) in k[t]/(V),
f= æ
ç
ç
è
n
å
i=1
Biwi
Vm
ö
÷
÷
ø		 '+
n
å
i=1
Ciwi
SGwUVm
    (3)
where
Ci=
GwAi
V
-SGwUBi'+ m
SGwUV'Bi
V
-
m
å
j=1
SGwUfj,iBj  Î k[t].     (4)

It remains to study under which circumstances the system (2) has a solution in k[t]/(V): we show that, whenever the system has no solution, we can extend the module k[t]w1+...+k[t]wn. Let
Si=SUVm+1 æ
ç
ç
è
wi
Vm
ö
÷
÷
ø		 ',  for   1£ i £ n.     (5)
Theorem 2   Suppose that m>0 and that { S1,...,Sn} as given by (5) are linearly independent over k(t), and let T1,...,Tn Î k[T] be not all zero and such that åi=1nTiSi=0. Then,
w=
SU
V
n
å
i=1
TiwiÎ O.
Furthermore, if gcd(T1,...,Tn)=1, then wÏ Ow=k[t]w1+··· k[t]wn.
Theorem 3   Suppose that m>0 and that { S1,...,Sn} as given by (5) are linearly independent over k(t), and let Q,T1,...,TnÎ k[t] be such that
n
å
i=1
Aiwi=
1
Q
n
å
i=1
TiSi.
Then,
w=
SU(V/gcd(V,Q))
gcd(V,Q)
n
å
i=1
TiwiÎ O.
Furthermore, if gcd(Q,T1,...,Tn)=1 and (2) has no solution in k[t]/(V), then wÏ Ow=k[t]w1+...+k[t]wn.

The lazy reduction algorithm follows from Theorems 1, 2, and 3: if m=0, then D=SU1, where S is special and Ui is normal. Otherwise, we solve the system
n
å
i=1
Aiwi=
n
å
i=1
hiSi
for h1,...,hn Î k(t). Any solution in k(t) whose denominators are coprime with V is a solution of (2) in k[t]/(V). In that case, (3) reduces integrating f to a new integrand whose denominator divides SGwUVm. If the above equation has no solution in k(t) whose denominators are coprime with V, then either the Si's are linearly dependent over k(t) or there is a solution whose denominator has nontrivial common factor with V, so either Theorem 2 or 3 produces wÎ O such that wÏ Ow, and the algorithm of Section 2 produces a new basis b1,...,bn for the submodule k[t]w+ Ow of  O. We transform that basis into an I-basis, express f in the new basis and continue the reduction process. In both of the above cases, the integrand after the reduction step has an expression whose denominator has strictly less zeroes of multiplicity m+1 than before (it has none when the system has a solution), so after finitely many reduction steps, we have produced a new basis made of integral elements, and a new integrand, whose denominator with respect to that basis is the product of a special and a normal polynomial. This is the same result as obtained by the Hermite reduction (with an integral basis) as presented in [1, 2, 7].

Conclusion

We have presented a lazy Hermite reduction for which each reduction step uses only rational operations and performs Gaussian or Hermitian elimination on matrices of size n by n or n+1 by n, while computing an integral basis requires Hermitian elimination on matrices of sizes n2 by n, so the lazy reduction is expected to cost O(n3) operations in k(t) as compared to O(n4) for computing rationally an integral basis. In the case of pure algebraic functions, this yields a complete algorithm for determining whether the integral of an algebraic function is itself an algebraic function. The natural direction in which to extend this work is to ask whether the complete algebraic integration algorithm can be performed rationally without computing an integral basis. Another interesting direction would be to generalize the Hermite reduction (and its lazy variant) to solve equations of the form y'+fy=g in a finitely generated algebraic extension of k(t), as was done for the transcendental case in [5]. This could yield a better algorithm than the reduction to a linear differential system in k(t) [3].

References

[1]
Bertrand (Laurent). -- Calcul Symbolique des Intégrales Hyperelliptiques. -- PhD thesis, Université de Limoges, Mathématiques, 1995.

[2]
Bronstein (Manuel). -- On the integration of elementary functions. Journal of Symbolic Computation, vol. 2, n°9, February 1990, pp. 117--173.

[3]
Bronstein (Manuel). -- The Risch differential equation on an algebraic curve. In Watt (Stephen) (editor), Symbolic and algebraic computation. pp. 241--246. -- New York, 1991. Proceedings of ISSAC'91, Bonn, Germany.

[4]
Bronstein (Manuel). -- Symbolic Integration I - Transcendental Functions. -- Springer, Heidelberg, 1997.

[5]
Davenport (James Harold). -- The Risch differential equation problem. SIAM Journal on Computing, vol. 15, 1986, pp. 903--918.

[6]
Lang (Serge). -- Algebra. -- Addison Wesley, Reading, Massachussets, 1970.

[7]
Trager (Barry). -- On the integration of algebraic functions. -- PhD thesis, MIT, Computer Science, 1984.
This document was translated from LATEX by HEVEA.