Change of orderng

When we compute a lex order Groebner basis, it is often efficient to compute it via Groebner basis with respect to another order such as degree reverse lex order, rather than to compute it directory by gr() etc. If we know that an input is a Groebner basis with respect to an order, we can apply special methods called change of ordering for a Groebner basis computation with respect to another order, without using Buchberger algorithm. The following two functions are ones for change of ordering such that they convert a Groebner basis gbase with respect to the variable order vlist1 and the order type order into a lex Groebner basis with respect to the variable order vlist2.

tolex(gbase,vlist1,order,vlist2)

This function can be used only when gbase is an ideal over the rationals. The input gbase must be a Groebner basis with respect to the variable order vlist1 and the order type order. Moreover the ideal generated by gbase must be zero-dimensional. This computes the lex Groebner basis of gbase by using the modular change of ordering algorithm. The algorithm first computes the lex Groebner basis over a finite field. Then each element in the lex Groebner basis over the rationals is computed with undetermined coefficient method and linear equation solving by Hensel lifting.

tolex_tl(gbase,vlist1,order,vlist2,homo)

This function computes the lex Groebner basis of gbase. The input gbase must be a Groebner basis with respect to the variable order vlist1 and the order type order. Buchberger algorithm with trace lifting is used to compute the lex Groebner basis, however the Groebner basis check and the ideal membership check can be omitted by using several properties derived from the fact that the input is a Groebner basis. So it is more efficient than simple repetition of Buchberger algorithm. If the input is zero-dimensional, this function inserts automatically a computation of Groebner basis with respect to an elimination order, which makes the whole computation more efficient for many cases. If homo is not equal to 0, homogenization is used in each step.

For zero-dimensional systems, there are several fuctions to compute the minimal polynomial of a polynomial and or a more compact representation for zeros of the system. They are all defined in `gr'. Refer to the sections for each functions.

Go to the first, previous, next, last section, table of contents.