Produit de séries formelles

Obtenir des algorithmes rapides pour le produit de séries formelles en plusieurs variables est un problème difficile, dont les applications ne manquent pas.

À la suite notamment des travaux de Schönhage, Bläser, Mulders, Hanrot et Zimmermann, Lecerf et Schost, van der Hoeven, on dispose de résultats partiels sur la question, mais on ne connaît pas encore d'algorithme de complexité optimale (quasi-linéaire) qui s'appliquerait en toutes circonstances.

Je montrerai comment la notion d'``algorithme approché" permet de ramener le produit de séries à des questions d'évaluation et d'interpolation en plusieurs variables. Cette approche permet de donner un algorithme de complexité quasiment linéaire dans un cas particulier important, la multiplication des séries tronquées en degré partiel.

Je présenterai des applications à l'addition des nombres algébriques, ainsi qu'à la résolution des systèmes polynomiaux.