Title Padé-Hermite approximants and eigenrings of skew-polynomials. Version française


BP 93, 06902 France


Manuel Bronstein


Skew-polynomials are linear operators that include differential and difference operators. They are used to represent linear differential, difference, or more general functional equations. The eigenring of a skew-polynomial L in K[X] is the ring of endomorphisms of the quotient module K[X]/K[X] L. That ring is useful in solving the corresponding functional equation L(y)=0 since its elements can be used to reduce that problem to solving equations of lower order. In the general case, eigenrings are computed via the companion system associated to the operator, which increases the complexity of the problem to computing eigenrings of systems. For differential equations, there is an efficient algorithm that works directly with operators [3].

Padé approximants are rational approximations of formal power series: a power series f(z) in F[[z]] is approximated by a rational function p(z)/q(z) where p(z) and q(z) are polynomials of bounded degree satisfying q(z) f(z) = p(z) + O(z^n) for an integer n large enough. Their generalization to a number of power series f1(z),...,fm(z) is a vector p1(z),...,pm(z) of polynomials such that p1(z)f1(z)+...+pm(z)fm(z) = O(z^n) for n large enough. There are fast (quadratic) algorithms for computing such approximants [1,2].

We have recently developped a new algorithm for the eigenring that works for skew polynomials without converting them to systems. This algorithm yields candidates for the endomorphisms that contain unknown constants. An efficient way to compute those constants would be to apply those candidates to a basis of formal power series solutions of the equation L(y)=0 and compute Padé-Hermite approximants of the resulting series. The goal of this internship is therefore to provide an efficient implementation of Padé-Hermite approximants, and to use them as an alternative in the implementation of the new eigenring algorithm for both the differential and difference equations. In addition, a variant based on Hensel-lifting truncated eigenring elements should be studied, implemented and compared to the Padé-Hermite approach.

[1] B.Beckermann & G.Labahn (1994): A Uniform Approach for the Fast Computation of Matrix-Type Pade Approximants, SIAM Journal on Matrix Analysis and Applications 15, pp. 804-823.
[2] H.Derksen (1994): An algorithm to compute generalized Padé-Hermite Forms, Report 9403, Dept. of Math., Catholic University Nijmegen.
[3] M.van Hoeij (1996): Rational solutions of the mixed differential equation and its application to factorization of differential operators, Proceedings of ISSAC'96, ACM Press, New York.


Unix workstation,  the Aldor programming language, with the Algebra library.


3 months.


November 8, 2004