François Vigneron (Reims) Nouveaux algorithmes pour les polynômes de haut degré.

Les questions de l'évaluation des polynômes et de la recherche de leurs racines constituent deux piliers de l'algorithmique moderne. Nous présenterons une série de résultats obtenus en collaboration avec Ramona Anton (SU) et Nicolae Mihalache (UPEC), à la fois théoriques et validés par des implémentations numériques. Concernant l'évaluation, il est possible d'utiliser la finitude de la précision à notre avantage pour obtenir une évaluation fiable dont la complexité moyenne est O(\sqrt(d)) au lieu de O(d), où d est le degré. Concernant l'éclatement, une nouvelle preuve EDO du théorème fondamental de l'algèbre conduit à une méthode basée sur les lignes de niveau et redoutablement efficace, qui a par exemple permis de trouver toutes les racines d'un polynôme de degré 10^{12} lié à l'ensemble de Mandelbrot, repoussant d'un facteur 1000+ l'état de l'art.