Localement, la méthode de Newton-Raphson pour trouver des racines de polynômes converge très rapidement. Pour scinder (ou éclater) un polynôme P de degré élevé d, nous disposons d'un résultat de Hubbard, Schleicher et Sutherland (2001) : il fournit un ensemble de O(d log^2 d) points de départ tel que toute racine de P soit une limite de la méthode de Newton. Il n'y a pas de borne supérieure sur le nombre de pas sur chaque orbite, mais il est assez facile de voir que l'ordre est au moins O(d). Je présenterai rapidement ce résultat et les autres méthodes usuelles pour scinder les polynômes.
Avec F. Vigneron, nous avons trouvé un algorithme (/ ensemble de points de départ) qui semble avoir une complexité quasi-linéaire, O(d) ou bien O(d log d) pour scinder une famille de polynômes liés à l'ensemble de Mandelbrot. Nous l'avons utilisé sur un super-calculateur pour éclater un polynôme de degré 2^40. Une nouvelle preuve du théorème fondamental de l'algèbre nous a aidé a mieux comprendre notre algoritme et ouvre la possibilité d'une généralisation de la méthode.
