TY - GEN
T1 - Gröbner basis over semigroup algebras
T2 - 44th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2019
AU - Bender, Matías R.
AU - Faugère, Jean Charles
AU - Tsigaridas, Elias
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2019/7/8
Y1 - 2019/7/8
N2 - Gröbner bases is one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with a 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. We consider sparse systems where the input polynomials have a few non-zero terms. Our approach to exploit sparsity is to embed the systems in a semigroup algebra and to compute Gröbner bases over this algebra. Up to now, the algorithms that follow this approach benefit from the sparsity only in the case where all the polynomials have the same sparsity structure, that is the same Newton polytope. We introduce the first algorithm that overcomes this restriction. Under regularity assumptions, it performs no redundant computations. Further, we extend this algorithm to compute Gröbner basis in the standard algebra and solve sparse polynomials systems over the torus (C∗)n. The complexity of the algorithm depends on the Newton polytopes.
AB - Gröbner bases is one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with a 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. We consider sparse systems where the input polynomials have a few non-zero terms. Our approach to exploit sparsity is to embed the systems in a semigroup algebra and to compute Gröbner bases over this algebra. Up to now, the algorithms that follow this approach benefit from the sparsity only in the case where all the polynomials have the same sparsity structure, that is the same Newton polytope. We introduce the first algorithm that overcomes this restriction. Under regularity assumptions, it performs no redundant computations. Further, we extend this algorithm to compute Gröbner basis in the standard algebra and solve sparse polynomials systems over the torus (C∗)n. The complexity of the algorithm depends on the Newton polytopes.
KW - Gröbner Basis
KW - Koszul Complex
KW - Mixed Sparse System
KW - Solving Polynomial System
KW - Sparse Elimination Theory
KW - Toric Variety
UR - https://www.scopus.com/pages/publications/85069782803
U2 - 10.1145/3326229.3326248
DO - 10.1145/3326229.3326248
M3 - Conference contribution
AN - SCOPUS:85069782803
T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
SP - 42
EP - 49
BT - ISSAC 2019 - Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation
PB - Association for Computing Machinery
Y2 - 15 July 2019 through 18 July 2019
ER -