Sharper Complexity Bounds for Zero-dimensional Gröbner Bases and Polynomial System Solving
Résumé
In this paper, we improve the bound of complexity of the algorithms on polynomial ideals having complexities polynomial in $d^n$ where $d$ is the maximal degree of input polynomials and $n$ the number of variables. Instead of this bound, we present the more accurate bound $\max{S,D^n}$ where $S$ is the size of the input polynomials in dense representation, and $D$ is the arithmetic mean value of the degrees of input polynomials.