Description
Date depot: 1 janvier 1900
Titre: Résolution des systèmes polynomiaux quasi-homogènes et Applications
Directeur de thèse:
Mohab SAFEY EL DIN (LIP6)
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 polynomiaux est un problème central en Calcul Formel du fait de ses nombreuses
applications dans de nombreux domaines des sciences de l’ingéniérie (sciences physiques, biologie, chimie, robotique)
et des sciences informatiques (cryptologie, géométrie algorithmique, vision, etc). Les méthodes de résolution
algébriques ont déjà montré leur intérêt dans au moins les deux domaines importants que sont la cryptanalyse
algébrique et la géométrie réelle et qui constituent les champs d’applications de cette thèse.
Les bases de Gröbner [2] constituent une brique essentielle pour la résolution [3]. Les nouvelles générations
d’algorithmes pour le calcul de bases de Gröbner (en particulier les algorithmes F4 et F5 [4, 5]) permettent aujourd’hui
la résolution d’applications hors de portée par d’autres méthodes. Ces algorithmes réduisent le problème de
calcul de bases de Gröbner à des problèmes d’algèbre linéaire (les polynômes sont codés comme des vecteurs de
monômes et on effectue des calculs de forme échelon). L’algorithme F5 a la particularité d’éviter de nombreux
calculs intermédiaires «inutiles» : en effet, des premières analyses ont montré que les matrices construites sont de
taille optimale dans le cas assez fréquent des systèmes réguliers [5]. Une fois la base de Gröbner obtenue, on peut
obtenir une paramétrisation rationnelle des solutions à l’aide de l’algorithme FGLM [6, 7], qui lui aussi repose sur
des calculs d’algèbre linéaires (polynômes minimaux).
Dans de très nombreuses applications, les systèmes polynomiaux qui apparaissent sont structurés ; en particulier
un grand nombre d’entre eux ont une structure quasi-homogène (une fois certaines variables élevées à
une certaine puissance, on obtient des polynômes homogènes), souvent pour des raisons liées à la physique du
problème.
À l’instar des résultats obtenus dans [1, 9, 8, 10, 11] analysant l’algorithme F5 dans le cas des systèmes surdéterminés
semi-réguliers, bi-linéaires et déterminantiels, il est naturel d’étudier et de chercher à améliorer cet
algorithme dans le but d’exploiter la structure quasi-homogène de ces systèmes.
La version classique de l’algorithme F5 ne permet pas d’éliminer tous les calculs inutiles dans le cas des
systèmes quasi-homogènes (les matrices construites ne sont pas de rang maximal si bien que des réductions à zéro
sont calculées). En effet, la série de Hilbert associée aux idéaux engendrés par des familles de polynômes quasihomogènes
(celle-ci permet de mesurer les chutes de rang dans les matrices considérées par l’algorithme F5) est
sensiblement différente de la série de Hilbert des idéaux homogènes. Un premier objectif est donc de s’appuyer
sur la connaissance de cette série de Hilbert dans le cas quasi-homogène pour modifier l’algorithme F5 de sorte à
obtenir un algorithme de calcul de bases de Gröbner exploitant la structure quasi-homogène en n’effectuant aucun
calcul inutile.
Un deuxième objectif est d’étudier la structure des matrices apparaissant dans la deuxième phase de la résolution
permettant d’obtenir les paramétrisations rationnelles. Dans les situations génériques, les matrices apparaissant
dans cette phase du calcul sont creuses : ceci permet de réduire fortement la complexité de cette étape du
calcul et l’exploitation du caractère creux de ces matrices débouche sur des progrès pratiques considérables [7].
Étudier l’impact des structures quasi-homogènes sur cette étape est donc primordial pour les applications.
Enfin, un troisième objectif est d’évaluer le coût de l’identification de la structure quasi-homogène d’un système
donné de manière à automatiser la chaîne complète de résolution
Références
[1] Bardet, M. and Faugère, J.C and Salvy B. Asymptotic expansion of the degree of regularity for semiregular
systems of equations. In P. Gianni, editor, Mega 2005 Sardinia (Italy), 2005.
[2] B. Buchberger. Gröbner Bases : an Algorithmic Method in Polynomial Ideal Theory. Recent trends in
multidimensional systems theory. Reider ed. Bose, 1985.
[3] 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.
[4] 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.
[5] 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.
[6] J.C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient Computation of Zero-dimensional Gröbner
Bases by Change of Ordering. Journal of Symbolic Computation, 16(4) :329-344, 1993.
[7] J.-C. Faugère and C. Mou. Fast Algorithm for Change of Ordering of Zero-dimensional Gröbner Bases
with Sparse Multiplication Matrices. In Proceedings of the 36th international symposium on Symbolic
and algebraic computation,
Doctorant.e: Verron Thibaut