Description
Date depot: 1 janvier 1900
Titre: Algorithmes efficaces pour le calcul des bases de Gröbner
Directeur de thèse:
Jean-Charles FAUGÈRE (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
La résolution des systèmes polynômiaux (systèmes non linéaires) est un problème central en Calcul Formel du fait de ses nombreuses applications. Les méthodes de résolution algébriques ont déjà montré leur intérêt dans plusieurs domaines parmi lesquels on peut citer : la Cryptologie (cryptanalyse algébrique), la géométrie algorithmique, la robotique, la théorie du signal, les codes correcteurs d’erreurs, ...
Les bases de Gröbner [1] constituent une brique essentielle pour la résolution des systèmes polynômiaux [2]. Comparé à l’algorithme originel de Buchberger pour le calcul de bases de Gröbner les algorithmes plus récents comme les algorithmes F4 et F5 [3, 4]
sont beaucoup plus efficaces et permettent aujourd’hui la résolution de systèmes provenant d’applications hors d’atteinte par d’autres méthodes. Ces algorithmes réduisent le problème du calcul des bases de Gröbner à une succession de problèmes d’algèbre linéaire de type réduction de Gauß (les polynômes sont alors codés comme des vecteurs
de monômes). L’algorithme F5 [4] a la particularité d’éviter de nombreux calculs intermédiaires «inutiles» et les matrices générées par l’algorithme sont de tailles optimales pour des systèmes vérifiant certaines hypothèses algébriques de régularité. L’objectif principal de la thèse est d’aller encore plus loin dans l’efficacité de ces algorithmes. D’une part il reste un très grand choix dans la manière de générer les matrices (par exemple, à taille
égale il faut mieux générer une matrice ayant une structure la plus proche possible d’une matrice triangulaire). D’autre part, un deuxième axe de recherche consistera a utiliser des
techniques similaires à celles utilisées pour le calcul rapide des pgcd de polynômes.
Les systèmes polynômiaux issus des applications ne sont en général pas aléatoires mais possèdent souvent une structure particulière (bilinéarité, polynômes creux,. . .). En particulier, pour un grand nombre de problèmes l’ensemble des solutions est laissé invariant
par l’action d’un groupe fini. Un autre objectif de la thèse sera de développer des algorithmes plus efficaces pour résoudre les systèmes présentant des symétries. Par exemple, le candidat pourra s’appuyer sur les travaux permettant le calcul rapide des bases Sagbi [6]. En effet, en utilisant la théorie des bases de Gröbner Sagbi on peut écrire chacune des équations de manière beaucoup plus creuse en utilisant l’action du groupe. On obtient ainsi une représentation compacte implicite des solutions en utilisant les fonctions élémentaires symétriques. Dans ce contexte un problème non résolu est
de lister efficacement et explicitement toutes les solutions. Pour cette partie du travail de thèse, le candidat pourra s’appuyer sur des exemples concrets de problèmes présentant des symétries provenant d’applications (par exemple certains problèmes en mécanique céleste).
-----------------------
Références
[1] B. Buchberger. Gröbner Bases : an Algorithmic Method in Polynomial Ideal Theory. Recent trends in multidimensional systems theory. Reider ed. Bose, 1985.
[2] D. A. Cox, J.B. Little, and D. O’Shea. Ideals, Varieties, and Algorithms : an Introduction
to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer-Verlag. New York, 1992.
[3] J.-C. Faugère. A New Efficient Algorithm for Computing Gröbner Basis : F4.
Journal of Pure and Applied Algebra, vol. 139, pp. 61–68, 1999.
[4] J.-C. Faugère. A New Efficient Algorithm for Computing Gröbner Casis without Reduction to Zero : F5. Proceedings of ISSAC, pp. 75–83. ACM press, July 2002.
[5] Bardet, M. and Faugère, J.C and Salvy B. Asymptotic expansion of the degree of regularity for semi-regular systems of equations. In P. Gianni, editor, Mega 2005 Sardinia (Italy), 2005.
[6] J.-C. Faugère and S. Rahmany. Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases. In ISSAC ’09 : Proceedings of the 2009 international symposium on Symbolic and algebraic computation, ISSAC ’09, pages 151-158, New York, NY, USA, 2009.
Doctorant.e: Svartz Jules