14h00: Algorithmes pour la décomposition primaire des idéaux polynomiaux de dimension nulle donnés en évaluation. Clémence Durvye, Département de Mathématiques de l'Université de Versailles Saint-Quentin-en-Yvelines.

Les algorithmes de résolution polynomiale sont impliqués dans des outils sophistiqués de calcul en géométrie algébrique aussi bien qu'en ingénierie. Les plus populaires d'entre eux reposent sur des bases de Gröbner, des matrices de Macaulay ou des décompositions triangulaires. Dans tous ces algorithmes, les polynômes sont développés dans une base des monômes et les calculs utilisent essentiellement des routines d'algèbre linéaire. L'inconvénient majeur de ces méthodes est l'explosion exponentielle du nombre de monômes apparaissant dans des polynômes éliminants. De manière alternative, l'algorithme Kronecker manie des polynômes codés comme la fonction qui calcule ses valeurs en tout point. Dans cet exposé, nous donnerons une présentation concise de ce dernier algorithme, et une idée de la preuve de son bon fonctionnement. La version de l'algorithme que nous présenterons calcule également les multiplicités des solutions sans coût supplémentaire. Ensuite, nous présenterons un algorithme de décomposition primaire pour les idéaux de polynômes de dimension nulle. Nous en donnerons également une étude de complexité précise, complexité qui est polynomiale en le nombre de variables, en le coût d'évaluation du système, et en un nombre de Bézout.