Title  Sharper complexity bounds for zerodimensional Gr\"obner bases and polynomial system solving. 
Author(s)  Amir Hashemi, Daniel Lazard 
Type  Article in Journal 
Abstract  The main purpose of this paper is to improve the bound of complexity of the wellknown algorithms on polynomial ideals having complexities polynomial in dn, where d is the maximal degree of input polynomials and n is the number of variables. Instead of this bound, we present the more accurate bound max{S, Dn} 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.

Keywords  Gröbner basis; complexity; polynomial system solving; Gaussian elimination; Macaulay matrix 
ISSN  02181967; 17936500/e 
URL 
http://www.worldscientific.com/doi/abs/10.1142/S0218196711006364 
Language  English 
Journal  Int. J. Algebra Comput. 
Volume  21 
Number  5 
Pages  703713 
Publisher  World Scientific, Singapore 
Year  2011 
Edition  0 
Translation 
No 
Refereed 
No 