A new algorithm for Gröbner bases conversion (Q6650576)

In 1965, Buchberger presented the notion of \textit{Gröbner bases} and also the first algorithmic method to compute them. Numerous efforts have been undertaken to enhance Buchberger's algorithm.\N\NIn this work a novel method for converting Gröbner bases of polynomial ideals over a field, regardless of dimension, is introduced. Unlike the existing approach relying on Gröbner fan and Gröbner walk for positive-dimensional ideals, this method is more intuitive, easier to prove, and simpler to implement. It works by defining a truncated sub-polynomial for each polynomial, containing monomials that could potentially become leading monomials under the target ordering, spanning the monomials between the leading terms of the initial and target orderings. The core of the proposed algorithm involves computing a Gröbner basis for the ideal generated by these truncated parts using the target ordering. This process employs an extended Buchberger algorithm, which also tracks the relationship between the input and output bases. This information facilitates the reconstruction of a Gröbner basis for the original ideal under the target ordering. Multiple iterations may be required, as truncated polynomials can sometimes overlook certain leading monomials. The algorithm has been implemented in Maple and demonstrated through an example. Its performance is benchmarked against other approaches within Maple, and for most cases, the target ordering Gröbner basis can be obtained in a single iteration. \N\NIn this paper, Section 3 introduces the concept of the truncated part of a polynomial relative to a pair of source and target orderings and explores its role in Gröbner basis conversion. Section 4 outlines the details of a new algorithm for converting Gröbner bases. In Section 5, the algorithm's performance is evaluated through a series of examples. Section 6 provides a brief overview of the Gröbner walk algorithm and examines its connection to the proposed method. The paper finishes with a discussion on potential directions for future research.