|Title||An Algorithm for Converting a Degree Gröbner basis to a Lexicographic Gröbner
|Author(s)|| Deepak Kapur, Tushar Saxena|
|Type||Technical Report, Misc|
|Abstract||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 <_2 such that it has that property. For termination condition, it is first checked whether all the polynomials in G_1 reduce to 0 modulo G, and if so, then check if G is a Gröbner basis. We prove that there is a T which will be generated within a finite number of steps for which the termination condition would succeed.|
The algorithm has been implemented in GEOMETER and has been successfully tried on a number of examples.