Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleSharper complexity bounds for zero-dimensional Gr\"obner bases and polynomial system solving.
Author(s) Amir Hashemi, Daniel Lazard
TypeArticle in Journal
AbstractThe main purpose of this paper is to improve the bound of complexity of the well-known 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
ISSN0218-1967; 1793-6500/e
URL http://www.worldscientific.com/doi/abs/10.1142/S0218196711006364
LanguageEnglish
JournalInt. J. Algebra Comput.
Volume21
Number5
Pages703--713
PublisherWorld Scientific, Singapore
Year2011
Edition0
Translation No
Refereed No
Webmaster