Skip to Main content Skip to Navigation
Conference papers

Towards Mixed Gröbner Basis Algorithms: the Multihomogeneous and Sparse Case

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download
Contributor : Matías Bender <>
Submitted on : Tuesday, May 15, 2018 - 2:09:50 PM
Last modification on : Tuesday, March 23, 2021 - 9:28:03 AM


Files produced by the author(s)



Matías Bender, Jean-Charles Faugère, Elias Tsigaridas. Towards Mixed Gröbner Basis Algorithms: the Multihomogeneous and Sparse Case. ISSAC 2018 - 43rd International Symposium on Symbolic and Algebraic Computation, Jul 2018, New York, United States. ⟨10.1145/3208976.3209018⟩. ⟨hal-01787423v2⟩



Record views


Files downloads