An Algorithm for Converting a Degree Grobner Basis to a Lexicographic Grobner Basis
Deepak Kapur, Tripti Saxena · 1995
An algorithm for converting a Gröbner basis, G 1 of an arbitrary ideal from one ordering ! 1 to a Gröbner basis G 2 with respect to another target ordering ! 2 is presented. Its behavior does not depend upon the dimension of the input ideal and it works for any positive or zero dimensional ideal. The target ordering can be any ordering including elimination orderings such as pure lexicographic. The algorithm is similar to the FGLM algorithm for basis conversion of zero dimensional ideals in the following sense: it incrementally constructs (i) a set T of terms, (ii) a set G of polynomials by computing the normal forms of the terms in T with respect to ! 1 and solving some linear equations similar to those in FGLM. However the order in which terms are generated in T is not completely determined by the target ordering ! 2 . If ! 2 does not have the property that for every term t, there are only finitely many terms smaller than t, then an enumeration ordering ! e is built using ! 1 and ...