Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Actualités

Séminaire de

Adrien Poteaux

24 février 2011
Amphi Turing, Bât M3

Un algorithme symbolique-numérique pour calculer au-dessus des points critiques d’une courbe algébrique plane

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 [2]. 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 de telles 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 ∈ K[x, y] un polynôme bivarié, où K est un corps de nombres (extension finie de Q), et notons C = {(x0 , y0 ) ∈ C2 | F (x0 , y0 ) = 0} la courbe algébrique plane associée. L’utilisation symbolique de l’algorithme de Newton-Puiseux conduit à e?ectuer des calculs dans des extensions de corps de degrés élevés (potentiellement, ce degré vaut D3 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 [3], qui est en O((dy)^{32+e} (dx)^{4+e}(log h)^{2+e}), où dy et dx 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.

A?n 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 séries de Puiseux.
Dans cet exposé, nous décrirons cette stratégie modulaire-numérique : après avoir décrit brièvement l’algorithme de Newton-Puiseux et les outils nécessaires à son utilisation, nous introduirons l’"arbre des polygones", contenant l’ensemble des informations exactes dont nous aurons besoin pour conduire nos calculs numériques. Ensuite, nous donnerons les principaux résultats permettant de calculer cet arbre à l’aide de calculs modulaires. En?n, nous montrerons sur un exemple la stratégie que nous utilisons pour suivre l’arbre des polygones lors du calcul numérique des coefficients des séries de Puiseux.
Ceci est un travail e?ectué dans le cadre de ma thèse [1] à l’université de Limoges, en collaboration avec Marc Rybowicz.

Références
[1] Adrien Poteaux. 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.
[2] R. J. Walker. Algebraic Curves. Springer-Verlag, 1950.
[3] P. G. Walsh. A Polynomial-time Complexity Bound for the Computation of the Singular Part of an Algebraic Function. Mathematics of Computation, 69 :1167–1182, 2000.

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster