14h00: Produit d'op�rateurs diff�rentiels par �valuation-interpolation. Nicolas Le Roux, �quipe Algorithms, Inria Paris-Rocquencourt.

Abstract Contrairement au cas commutatif o� le produit de polyn�mes a �t� intensivement �tudi� et son importance dans de nombreux algorithmes de base en calcul formel mise en �vidence, le produit de polyn�mes tordus, et en particulier le produit d'op�rateurs diff�rentiels, n'a pratiquement pas �t� abord� du point de vue algorithmique. Tr�s r�cemment, Joris van der Hoeven a montr� que le produit d'op�rateurs diff�rentiels (en caract�ristique nulle) peut se ramener � un nombre constant de produits de matrices par un algorithme d'�valuation-interpolation. Il a de plus pos� la question suivante : Peut-on r�duire un produit de matrices � un nombre constant d'op�rateurs diff�rentiels? Dans un premier temps, l'expos� r�pondra par l'affirmative � cette question dans le cas o� les op�rateurs ont des degr�s et des ordres de taille comparable, n. Cette r�ponse positive s'obtient : - d'une part en montrant, gr�ce � un r�sultat de A. Bostan et E. Schost, que les complexit�s arithm�tiques de l'�valuation et de l'interpolation dans l'algorithme de J. van der Hoeven peuvent �tre rendues quasi-lin�aires en la taille de la sortie, r�duisant entre autre le nombre de produits de matrices carr�es de taille n n�cessaire ; - d'autre part en renversant l'algorithme, donnant lieu � un algorithme d'interpolation-�valuation pour le produit de matrices carr�es de taille n. Ceci montre qu'une approche d'�valuation-interpolation est optimale pour le produit d'op�rateurs diff�rentiels d'ordres et degr�s de m�me taille. J'expliquerai ensuite comment ce nombre de produits de matrices peut �tre r�duit un peu plus, gr�ce � un nouvel algorithme d'�valuation-interpolation. Celui-ci est plus direct que celui de J. van der Hoven dans le sens o� il �vite de r��crire les op�rateurs diff�rentiels comme polyn�mes tordus en la d�riv�e d'Euler. Je discuterai ensuite de la question de l'�quivalence entre produit d'op�rateurs diff�rentiels et produit de matrices dans d'autres cas de figure : - en petite caract�ristique, o� l'approche par �valuation-interpolation n'est plus valable. Nous donnons un nouvel algorithme, de complexit� quasi-lineaire en la taille de la sortie, rendant hypoth�tique une r�ponse positive � l'�quivalence ci-dessus ; - en caract�ristique 0, dans le cas o� la taille entre les ordres et les degr�s sont d�s�quilibr�s. Certains algorithmes du folklore se r�v�lent alors meilleurs, en l'�tat actuel de nos connaissances sur le co�t du produit matriciel. Ils interrogent sur la question de l'�quivalence avec le produit de matrices. Je discuterai enfin de certains cas qu'on peut rencontrer en pratique, notamment pour le calcul de bases de Gr�bner de polyn�mes tordus : un des op�randes du produit a tr�s peu de termes. Je donnerai diff�rents cas pour lesquels, une approche par �valuation-interpolation, mais sans produit matriciel cette fois-ci, permet de gagner sur l'algorithme d'�valuation-interpolation propos�. (Travail en collaboration avec Alin Bostan et Fr�d�ric Chyzak)