HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Complexity of Zero-dimensional Gröbner Bases

Amir Hashemi 1, 2 Daniel Lazard 1, 2
1 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : In this paper, it is shown that the Gröbner basis (for any monomial ordering) of a zero-dimensional ideal may be computed within a bit complexity which is essentially polynomial in $D^n$ where $n$ is the number of unknowns and $D$ the mean value of the degrees of input polynomials. Therefore, if all input polynomials have the same degree, this complexity is polynomial in the maximum of the input size and of the output size, for almost all inputs. The proof is designed in order that it may be generalized to the case of an ideal generated by a regular sequence and for the degree reverse lexicographic ordering, when the last variables are in generic position for the ideal. But one step of the proof is yet lacking in this case.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:13:32 PM
Last modification on : Friday, February 4, 2022 - 3:07:58 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:00:44 PM


  • HAL Id : inria-00070348, version 1


Amir Hashemi, Daniel Lazard. Complexity of Zero-dimensional Gröbner Bases. [Research Report] RR-5660, INRIA. 2005, pp.29. ⟨inria-00070348⟩



Record views


Files downloads