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)