责任导师 : Jean-Charles FAUGÈRE

助理责任导师 : 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.

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”, 博士论文, 答辩 2019-6-3, 责任导师 Faugère, Jean-Charles, 助理责任导师 : 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 - 44^th 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 - 43^rd 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 - 43^rd 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 - 41^st International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, pp. 79-86, (ACM) (2016)