Details:
Title  Complexity of Buchberger's algorithm for Grobner bases  Author(s)  Thomas W. Dubé, Bud Mishra, CheeK. K. Yap  Type  Technical Report, Misc  Abstract  In 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.  Length  17 
File 
 Language  English  Year  1995  Translation 
No  Refereed 
No 
