Séminaire du 23 mai 05, by
Bruno Salvy, Projet Algorithmes.
Solutions polynomiales et rationnelles d'équations
différentielles ou de récurrences linéaires
La recherche de solutions rationnelles est au coeur de nombreux algorithmes du calcul formel en sommation, intégration, définie ou indéfinie, ou en recherche de solutions liouvilliennes. Mˆme pour la simple question de l'existence de solutions polynomiales, il n'existe pas d'algorithme général en complexité polynomiale. Cependant, les solutions polynomiales de degré élevé sont très contraintes par l'équation. Ceci permet de les représenter par une structure de données compacte : une récurrence et des conditions initiales. Cette structure de données autorise un calcul en complexité quasi-optimale (optimale à des logarithmes près) des solutions, de leurs valeurs et de celles de leurs dérivées en tout point rationnel ou plus généralement à coordonnées algébriques; elle permet également la division par une puissance élevé d'un monôme, d'où découle un calcul en complexité quasi-optimale des solutions rationnelles. Ces résultats de complexité sont directement visibles sur les temps de calculs de nos implantations en Maple et en Magma. Je profiterai de l'exposé pour faire une description des jolis algorithmes sur des questions proches. Le travail dont est issu cet exposé a été effectué en commun avec Alin Bostan et Thomas Cluzeau.
Virginie Collette
Last modified: Mon Jan 10 15:32:34 CET 2005