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


TitleComplexity of Buchberger's algorithm for Grobner bases
Author(s) Thomas W. Dubé, Bud Mishra, Chee-K. K. Yap
TypeTechnical Report, Misc
AbstractIn computational algebraic geometry, Buchberger's algorithm for constructing a Gröbner basis has been recognized as a fundamental tool. Despite great interest in analyzing the complexity of this algorithm, relatively little progress has been made. We undertake a systematic study of his algorithm. The concepts of admissible orderings and normal form algorithm are basic in Buchberger's algorithm. We present a new constructive and elemantary proof of Robbiano's characterization theorem for admissible orderings. Using this characterization, we give a bound on the complexity of the normal form algorithm for arbitrary admissible orderings. Next we obtain for the first time a complexity analysis for the overall algorithm, showing that for each fixed number of variables, the complexity is in the finite Wainer hierarchy, and hence primitive recursive. Again, these results hold for arbitrary admissible ordering.
Translation No
Refereed No