Projet de recherche doctoral numero :3935

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