Supervision : Jean-Charles FAUGÈRE
Co-supervision : TSIGARIDAS Elias
Algorithms for sparse polynomial systems : Gröbner bases and resultants
Polynomial system solving is one of the oldest and most important problems in computational mathematics and has many applications in computer science. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. In this thesis we focus on exploiting the structure related to the sparsity of the supports of the polynomials; that is, we take advantage of the fact that the polynomials only have a few monomials with non-zero coefficients. Our objective is to solve sparse systems faster than the worst case estimates that assume that all the terms are present. We develop algorithms for mixed sparse polynomial systems, that is, systems where the sparsity structure of the polynomials (Newton polytope) is different. We elaborate on two domains of elimination theory: sparse resultants and Gröbner bases. We work on each domain independently, but we also combine them to introduce new algorithms showing for the first time their relation in the sparse setting. We build on the multigraded Castelnuovo-Mumford regularity to develop this relation. We use resultants to propose "optimal" algorithms to solve families of mixed multilinear systems and, for a more general setting, we use Gröbner bases to solve sparse systems avoiding useless computations. The complexity of our algorithms depends on the sparsity structure of the systems (Newton polytopes). Finally, we introduce quasi-optimal algorithms to decompose binary forms.
Phd defence : 06/03/2019
Jury members :
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
Departure date : 06/15/2019
2016-2021 Publications
-
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”, thesis, phd defence 06/03/2019, supervision Faugère, Jean-Charles, co-supervision : 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)