Séminaire du 29 mars 04, Alin Bostan.

Sur les complexités de l'évaluation et de l'interpolation

L'évaluation multipoint est une opération d'importance majeure en calcul formel : étant donné un polynôme $P$ de degré $n$, il s'agit de déterminer les valeurs que prend $P$ sur un ensemble de $n+1$ points.

Dans cet exposé, nous décrivons de nouveaux algorithmes pour ce problème, ainsi que pour la question inverse, l'interpolation. Nous étudions en particulier des cas où les points d'évaluation forment une progression arithmétique ou géométrique. Pour toutes ces questions, nous améliorons la complexité des meilleurs algorithmes connus. L'efficacité de nos algorithmes repose sur l'utilisation de la multiplication transposée des polynômes et, plus généralement, du principe de transposition de Tellegen.

Comme conséquences, nous obtenons des accélérations d'un spectre varié d'algorithmes classiques concernant l'arithmétique des matrices polynomiales, la factorisation des entiers ou encore la manipulation des suites récurrentes à coefficients polynomiaux.

Les résultats présentés ont éét obtenus en collaboration avec P. Gaudry (LIX), G. Lecerf (LAMA) et É. Schost (STIX).