TY - GEN
T1 - Towards mixed gröbner basis algorithms
T2 - 43rd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2018
AU - Bender, Matías R.
AU - Faugère, Jean Charles
AU - Tsigaridas, Elias
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/7/11
Y1 - 2018/7/11
N2 - One of the biggest open problems in computational algebra is the design of efficient algorithms for Gröbner basis computations that take into account the sparsity of the input polynomials. We can perform such computations in the case of unmixed polynomial systems, that is systems with polynomials having the same support, using the approach of Faugère, Spaenlehauer, and Svartz [ISSAC’14]. We present two algorithms for sparse Gröbner bases computations for mixed systems. The first one computes with mixed sparse systems and exploits the supports of the polynomials. Under regularity assumptions, it performs no reductions to zero. For mixed, square, and 0-dimensional multihomogeneous polynomial systems, we present a dedicated, and potentially more efficient, algorithm that exploits different algebraic properties that performs no reduction to zero. We give an explicit bound for the maximal degree appearing in the computations.
AB - One of the biggest open problems in computational algebra is the design of efficient algorithms for Gröbner basis computations that take into account the sparsity of the input polynomials. We can perform such computations in the case of unmixed polynomial systems, that is systems with polynomials having the same support, using the approach of Faugère, Spaenlehauer, and Svartz [ISSAC’14]. We present two algorithms for sparse Gröbner bases computations for mixed systems. The first one computes with mixed sparse systems and exploits the supports of the polynomials. Under regularity assumptions, it performs no reductions to zero. For mixed, square, and 0-dimensional multihomogeneous polynomial systems, we present a dedicated, and potentially more efficient, algorithm that exploits different algebraic properties that performs no reduction to zero. We give an explicit bound for the maximal degree appearing in the computations.
KW - Mixed Sparse Gröbner Basis
KW - Multihomogeneous Polynomial System
KW - Sparse Polynomial System
KW - Toric variety
UR - https://www.scopus.com/pages/publications/85054935897
U2 - 10.1145/3208976.3209018
DO - 10.1145/3208976.3209018
M3 - Conference contribution
AN - SCOPUS:85054935897
T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
SP - 71
EP - 78
BT - ISSAC 2018 - Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation
PB - Association for Computing Machinery
Y2 - 16 July 2018 through 19 July 2018
ER -