Calcul pratique des séries de Puiseux

Les séries de Puiseux (généralisation des séries de Taylor au-dessus des points critiques) sont un outil fondamental de la
théorie des courbes algébriques [3]. Néanmoins, le calcul de ces séries n'est pas une tache aisée. En effet, il n'existe que des algorithmes symboliques pour calculer ces développements : les logiciels permettant le calcul de ces séries
utilisent l'algorithme de Newton-Puiseux, et une utilisation purement
numérique de cet algorithme retourne des séries de Taylor ayant un
rayon de convergence très petit. Ainsi, cela ne permet pas de trouver la structure des séries, qui est la raison même de
calculer ces séries. D'un autre côté, un calcul purement symbolique des séries de Puiseux est fortement coûteux en temps.

Plus précisément, notons $F\in K[x,y]$ un polynôme bivarié, où
$K$ est un corps de nombres, et notons ${\cal C} = \{(x_0,y_0)\in C^2 \mid F(x_0,y_0)=0\}$ la courbe algébrique plane associée. L'utilisation symbolique de l'algorithme de Newton-Puiseux
conduit à  effectuer des calculs dans des extensions de corps de
degrés élevés (potentiellement, ce degré vaut $D^3$ si $D$ est
le degré total du polynôme considéré), et on assiste de plus à  un
phénomène de croissance des coefficients important. Tout cela est
résumé dans la complexité binaire donnée par P.G. Walsh [4], qui est en $O(d_y^{32+\epsilon}d_x^{4+\epsilon}
(\log h)^{2+\epsilon})$, où $d_y$ et $d_x$ sont respectivement les degrés en $y$ et $x$ du polynôme $F$, et $h$ est sa hauteur. Même si
cette borne n'est peut-être pas optimale, les expériences montrent bien qu'en pratique, les calculs effectuables sont vite limités.

Afin d'obtenir une méthode permettant une utilisation pratique des
développements de Puiseux, nous avons développé la stratégie
suivante~:

1) Trouver la structure des séries de Puiseux à  l'aide de calculs modulo un nombre premier $p$ ``bien choisi'',

2) Utiliser cette structure pour calculer numériquement les coefficients des séries de Puiseux.

Dans cet exposé, après avoir évoqué nos motivations et rappelé le fonctionnement de l'algorithme de Newton-Puiseux (et plus
précisément sa version rationnelle [1]), nous
décrirons notre critère de réduction nous permettant de garantir
la préservation de la structure des séries par réduction modulaire, puis nous donnerons brièvement les idées utilisées
pour calculer une approximation numérique des coefficients à  l'aide
de cette structure. Enfin, nous parlerons de la complexité algorithmique de l'algorithme de Newton Puiseux, en présentant quelques idées et résultats vers un algorihtme rapide.

Ceci est un travail initié dans le cadre de ma thèse [2] à  l'université de Limoges, en collaboration avec Marc Rybowicz.

Bibliographie

[1] D. Duval. Rational {P}uiseux
{E}xpansions. {\em Compositio Mathematica}, 70:119--154, 1989.

[2] Adrien Poteaux. {\em Calcul de développements de Puiseux et application au calcul de groupe de monodromie d'une courbe algébrique plane}. PhD thesis, Université de Limoges, 2008.

[3] R.~J. Walker.{\em Algebraic Curves}. Springer-Verlag, 1950.

[4] P.~G. Walsh. A {P}olynomial-time {C}omplexity {B}ound for the {C}omputation of the {S}ingular {P}art of an {A}lgebraic {F}unction. {\em Mathematics of Computation}, 69:1167--1182, 2000.