Direction de recherche : Jean-Charles FAUGÈRE
Co-encadrement : TSIGARIDAS Elias
Algorithmes pour les systèmes polynomiaux creux : bases de Gröbner et résultants
La résolution de systèmes polynomiaux est l’un des problèmes les plus anciens et les plus importants en mathématique, et a de nombreuses applications en informatique. C'est un problème intrinsèquement difficile avec une complexité au moins exponentielle en le nombre de variables. Cependant, dans la plupart des cas, les systèmes polynomiaux issus d'applications ont une structure particulière. Dans cette thèse, nous exploitons le caractère creux des polynômes ; c'est-à-dire que nous tirons parti du fait que les polynômes n'ont qu'un petit nombre de termes non nuls. Nous développons des algorithmes pour les systèmes polynomiaux mixtes et creux, c'est-à-dire pour lesquels la structure creuse de chaque polynôme (polytope de Newton) est différente. Nous contribuons dans deux domaines de la théorie de l'élimination : les résultants creux et les bases de Gröbner. Nous travaillons de manière indépendante sur chaque domaine, mais nous les combinons aussi pour introduire de nouveaux algorithmes, établissant pour la première fois un lien entre ces deux domaines dans le contexte creux. Pour cela, nous nous appuyons sur la régularité multigraduée de Castelnuovo-Mumford. Nous utilisons les résultants pour proposer des algorithmes «optimaux» permettant de résoudre des familles de systèmes mixtes multilinéaires et, dans le cas général, nous utilisons les bases de Gröbner pour résoudre les systèmes creux en évitant les calculs inutiles. La complexité de nos algorithmes dépend de la structure creuse des systèmes (polytopes de Newton). Nous proposons également des algorithmes quasi-optimaux pour décomposer les formes binaires.
Soutenance : 03/06/2019
Membres du jury :
M. Carlos D'Andrea, Professor Agregat, Universitat de Barcelona [Rapporteur]Mme. Agnes Szanto (rapporteuse), Professor, North Carolina State University [Rapporteur]
M. Laurent Busé, Chargé de recherche, INRIA - Sophia Antipolis
M. Jean-Charles Faugère, Directeur de Recherche, INRIA - Paris
M. Stef Graillat, Professeur, Sorbonne Université
M. Bernard Mourrain, Directeur de Recherche, INRIA - Sophia Antipolis
M. Elias Tsigaridas, Chargé de recherche, INRIA - Paris
M. Gilles Villard, Directeur de recherche, CNRS - INS2I
Date de départ : 15/06/2019
Publications 2016-2021
-
2021
- M. Bender, J.‑Ch. Faugère, A. Mantzaflaris, E. Tsigaridas : “Koszul-type determinantal formulas for families of mixed multilinear systems”, SIAM Journal on Applied Algebra and Geometry, vol. 5 (4), pp. 589-619, (Society for Industrial and Applied Mathematics) (2021)
- M. Bender, J.‑Ch. Faugère, L. Perret, E. Tsigaridas : “A nearly optimal algorithm to decompose binary forms”, Journal of Symbolic Computation, vol. 105, pp. 71-96, (Elsevier) (2021)
-
2019
- M. Bender : “Algorithms for sparse polynomial systems : Gröbner bases and resultants”, soutenance de thèse, soutenance 03/06/2019, direction de recherche Faugère, Jean-Charles, co-encadrement : Tsigaridas, Elias (2019)
- M. Bender, J.‑Ch. Faugère, E. Tsigaridas : “Gröbner Basis over Semigroup Algebras: Algorithms and Applications for Sparse Polynomial Systems”, ISSAC 2019 - 44th International Symposium on Symbolic and Algebraic Computation, Beijing, China, pp. 42-49, (ACM) (2019)
-
2018
- M. Bender, J.‑Ch. Faugère, A. Mantzaflaris, E. Tsigaridas : “Bilinear systems with two supports: Koszul resultant matrices, eigenvalues, and eigenvectors”, ISSAC 2018 - 43rd International Symposium on Symbolic and Algebraic Computation, New York, United States (2018)
- M. Bender, J.‑Ch. Faugère, E. Tsigaridas : “Towards Mixed Gröbner Basis Algorithms: the Multihomogeneous and Sparse Case”, ISSAC 2018 - 43rd International Symposium on Symbolic and Algebraic Computation, New York, United States (2018)
-
2016
- M. Bender, J.‑Ch. Faugère, L. Perret, E. Tsigaridas : “A Superfast Randomized Algorithm to Decompose Binary Forms”, ISSAC '16 - 41st International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, pp. 79-86, (ACM) (2016)