On the complexity of computing grobner bases for zero-dimensional polynomial ideals
Erich Kaltofen, Lakshman Yagati · Medical Entomology and Zoology · 1990
Grobner Bases have come to occupy a central place in Computational Algebra due to the wide range of problems that they help to solve. The problems that can be tackled include testing for ideal membership, testing for radical membership, deciding invertibility of polynomial maps and equation solving, to name a few. Because of its applicability, there is a great interest in designing efficient algorithms for computing Grobner bases and a need to understand the complexity of any such algorithm. It is also known that the computation of Grobner bases is very hard in general (due to the exponential space lower bound on the complexity of testing for ideal membership, shown by Mayr and Meyer). However, it is worthwhile investigating whether Grobner bases can be computed for interesting sub-families of ideals, in much less time than that implied by Mayr and Meyer's doubly exponential lower bound. In this thesis, we investigate the complexity of computing Grobner bases for zero-dimensional ideals in the ring of polynomials in n variables with rational number coefficients. Given a zero-dimensional ideal presented by a finite basis $\{f\sb1,f\sb2,...,f\sb{r}\}$ with the degrees of $f\sb{i}$ bounded by d, we show an $O(d\sp{cn}$) (for a small constant c) upper bound on the number of operations (+,$-$,$\times$,/) involving rational numbers needed to compute reduced Grobner bases for the ideal, its radical and all of its primary components. This bound improves the previously known bound of $O(r\sp3 d\sp{O(n\sp3)}).$ The main tools of our investigation are generalized Macaulay resultants and the change of basis algorithm of Faugere, Gianni, Lazard and Mora. Our strategy is to compute a Grobner basis for the radical of the given ideal first, using a generalization of Macaulay's resultant. We then compute Grobner bases for all the associated prime ideals from which we construct Grobner bases for each of the primary ideals that contains the given ideal. The Grobner bases for the primary ideals are then stitched together to obtain a Grobner basis for the original ideal. We also generalize the change of basis algorithm of Faugere et al to derive efficient new algorithms for computing Grobner bases for intersections, quotients and images under linear transformations for zero-dimensional ideals.