| Titre Approximants de Padé-Hermite et eigenrings de polynômes de Ore. | English
version |
Lieu
INRIA, Projet
CAFÉ
BP 93, 06902 France
Information
Description
Les polynômes de Ore sont des opérateurs linéaires qui contiennent en particulier les opérateurs différentiels et aux différences finies. Ils sont utiles pour représenter les équations linéaires, qu'elles soient différentielles, aux différences, ou bien plus générales. L'eigenring d'un polynôme de Ore L de K[X] est l'anneau des endomorphismes du module quotient K[X]/K[X] L. Cet anneau sert à résoudre l'équation fonctionnelle L(y)=0 car ses éléments sont utilisés pour réduire ce problème à la résolution d'équations d'ordre plus petit. Dans le cas général, on passe par le système compagnon de l'opérateur pour calculer son eigenring, ce qui augmente la complexité puisqu'on calcule l'eigenring d'un système. Dans le cas des équations différentielles, il existe un algorithme efficace qui travaille directement avec les opérateurs [3].
Les approximants de Padé sont des approximations rationelles de séries formelles : une série f(z) in F[[z]] est approximée par une fonction rationelle p(z)/q(z) où p(z) et q(z) sont des polynômes de degré borné tels que q(z) f(z) = p(z) + O(z^n) pour un entier n suffisamment grand. Leur généralisation à un nombre arbitraire de séries f1(z),...,fm(z) est un vecteur p1(z),...,pm(z) de polynômes tels que p1(z)f1(z)+...+pm(z)fm(z) = O(z^n) pour n suffisamment grand. Il existe des algorithmes rapides (quadratiques) pour calculer de tels approximants [1,2].
Nous développons dans le projet un nouvel algorithme de calcul de l'eigenring qui travaille directement sur les polynômes de Ore sans les convertir en systèmes. Cet algorithme produit des candidats pour les endomorphismes qui contiennent des constantes indéterminées. Une méthode efficace pour déterminer ces constantes serait d'appliquer ces candidats à une base de solutions formelles de l'équation L(y)=0 et de calculer des approximants de Padé-Hermite des séries obtenues. Le but de ce stage est donc d'implémenter efficacement les approximants de Padé-Hermite et de les utiliser comme alternative dans l'implémentation du nouvel algorithme autant pour les équations différentielles que pour les équations aux différences. De plus, une autre variante basée sur le relèvement de Hensel d'éléments tronqués de l'eigenring est à étudier, implémenter et comparer avec l'approche des approximants de Padé-Hermite.
[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.
Outils
Station de travail Unix, langage de programmation Aldor, avec la bibliothèque Algebra.
Durée
3 mois, niveau stage d'ingénieur ou Master.