Équipe et Contacts
Équipe Calcul Formel.
François Boulier : Francois.Boulier@univ-lille1.fr
Alexandre Sedoglavic : Alexandre.Sedoglavic@univ-lille1.fr
Mots-Clefs
Élimination algébrique. Aspects effectifs. Bases de Gröbner
Sujet
Dans de très nombreuses applications (cryptologie, système dynamique, etc.), on considère une formulation géométrique du problème sous la forme de points d'un espace affine. Ces points sont souvent décrits comme les zéros de polynômes.
Par exemple, on peut représenter les points d'intersections d'un cercle de rayon 2 et d'une hyperbole par les équations algébriques x^2+y^2-2=0 et xy-1=0. Ces points peuvent aussi être représentés par les équations y^4-2y^2+1=0 et x-2y+y^3=0 (qui ont le mérite de réduire l'estimation numérique des points à une quadrature classique et une paramétrisation de x).
Cette dernière représentation est une base de Gröbner (pour un certain ordre) de l'ensemble des équations représentant les points en question.
Ce type de base a été popularisé dans les années 1960 par Bruno Buchberger, qui lui a donné le nom de son directeur de thèse Wolfgang Gröbner. Il permet - entre autre - de décider si un ensemble de relation est cohérent (i.e. représente un ensemble de points non vide), si un polynôme s'annule sur ces points et de calculer des invariants géométriques de ces points (dimension, degré).
L'algorithme de Buchberger qui permet de calculer une base de Gröbner est une généralisation multivariée de l'algorithme d'Euclide univarié pour le calcul du pgcd et non linéaire de l'algorithme d'élimination de Gauss pour les systèmes linéaires. Cet algorithme admet des généralisations dans le cadre différentiel qui est un domaine de compétence de l'équipe de calcul formel du LIFL.
Les algorithmes et implantations les plus efficaces actuellement de calcul de base de Gröbner sont l'oeuvre de Jean-Charles Faugère (CNRS, INRIA Rocquancourt).
Une nouvelle approche a émergé très récement dans les travaux de S. Gao, Y.Guan F. Volny et M. Wang dont les résultats expérimentaux semblent très prometteurs.
Travail à mener
Le sujet du stage consiste en l'étude détaillé de cet algorithme que ce soit sur le plan théorique et expérimental.
Poursuite
Une poursuite en thèse est possible