A fast algorithm for Gröbner basis conversion and its applications (Q1588033): Difference between revisions

The Gröbner walk method converts a Gröbner basis by partitioning the computation of the basis into several smaller computations following a path in the Gröbner fan of the ideal generated by the system of equations. Typically, the target point of the walking path leads to initial forms of great numbers of terms. Up to now, the best way to avoid this was to choose the point heuristically. In this paper, the author improves the Gröbner walk method by giving a deterministic procedure to vary this target point in order to ensure the generality of the position (that means that the initial forms have always a few terms). The author uses a bound for the total degree of the polynomials in a Gröbner basis due to \textit{T. W. Dubé} [SIAM J. Comput. 19, 750-773 (1990; Zbl 0697.68051)] and a result which relates weight vectors to term orders [\textit{D. Eisenbud}, Commutative algebra. With a view towards algebraic geometry, Graduate Texts Math. 150 (1995; Zbl 0819.13001)]. Then he proves the main theorem of the paper which states that, given any admisible term order, a particular weight vector which represents the Gröbner cone of an ideal with respect to this term order can be found deterministically. Afterwards, the author proposes an algorithm for basic conversion and shows many examples and applications of his method. The method is said to be much faster than the direct computation of the reduced Gröbner basis with respect to the pure lexicographic term order using Buchberger algorithm.