Supervision : Jean-Charles FAUGÈRE

Algorithmes efficaces pour le calcul des bases de Gröbner

Les systèmes polynomiaux à plusieurs variables apparaissent naturellement dans de nombreux domaines scientifiques. Ces systèmes issus d'applications possèdent une structure algébrique spécifique. Une méthode classique pour résoudre des systèmes polynomiaux repose sur le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de systèmes structurés, lorsque la structure est induite par l'action d'un groupe (systèmes avec symétries) ou une structure monomiale particulière, (qui inclut notamment les systèmes multi-homogènes ou quasi-homogènes). D'une part, cette thèse propose de nouveaux algorithmes qui exploitent ces structures algébriques pour améliorer l'efficacité de la résolution de systèmes (systèmes invariant sous l'action d'un groupe ou à support dans un ensemble de monômes particuliers). Ces techniques permettent notamment de résoudre un problème issu de la physique pour des instances hors de portée jusqu'à présent. D'autre part, ces outils permettent d'améliorer les bornes de complexité de résolution de plusieurs familles de systèmes polynomiaux structurés (systèmes globalement invariant sous l'action d'un groupe abélien, individuellement invariant sous l'action d'un groupe quelconque, ou ayant leur support dans un même polytope). Ceci permet en particulier d'étendre des résultats connus sur les systèmes bilinéaires aux systèmes multi-homogènes généraux.

2012-2016 Publications

• 2016
  • J.‑Ch. Faugère, P.‑J. Spaenlehauer, J. Svartz : “Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems”, Proceedings of ISSAC 2016, Waterloo, Canada, pp. 223-230, (ACM) (2016)
• 2014
  • J. Svartz : “Algorithmes efficaces pour le calcul des bases de Gröbner”, thesis, defence 10/30/2014, supervision Faugère, Jean-Charles (2014)
  • J.‑Ch. Faugère, P.‑J. Spaenlehauer, J. Svartz : “Sparse Gröbner Bases: the Unmixed Case”, ISSAC 2014, Kobe, Japan (2014)
• 2013
  • J.‑Ch. Faugère, J. Svartz : “Gröbner Bases of Ideals Invariant under a Commutative Group: the Non-Modular Case”, Proceedings of the 38^th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, Boston, United States, pp. 347-354, (ACM) (2013)
• 2012
  • J.‑Ch. Faugère, J. Svartz : “Solving Polynomial Systems Globally Invariant Under an Action of the Symmetric Group and Application to the Equilibria of N vortices in the Plane”, ISSAC '12 - International Symposium on Symbolic and Algebraic Computation, Grenoble, France, pp. 170-178, (ACM) (2012)