FGLM -- Compute Groebner bases via the FGLM algorithm

Description

FGLM is a Groebner basis conversion algorithm. This means it takes a Groebner basis of an ideal with respect to one monomial order and changes it into a Groebner basis of the same ideal over a different monomial order. Conversion algorithms can be useful since sometimes when a Groebner basis over a difficult monomial order (such as lexicographic or an elimination order) is desired, it can be faster to compute a Groebner basis directly over an easier order (such as graded reverse lexicographic) and then convert rather than computing directly in the original order. Other examples of conversion algorithms include the Groebner walk and Hilbert-driven Buchberger.

FGLM performs conversion by doing linear algebra in the quotient ring R/I, where I is the ideal generated by the original Groebner basis in the polynomial ring R. This requires that I is zero-dimensional.

In Macaulay2, monomial orders must be given as options to rings. For example, the following ideal has monomial order given by graded reverse lexicographic (which is also the default order in Macaulay2).

i1 : R1 = QQ[x,y,z, MonomialOrder => GRevLex]

o1 = R1

o1 : PolynomialRing

i2 : I1 = ideal(x*y + z - x*z, x^2 - z, 2*x^3 - x^2*y*z - 1)

                            2         2        3
o2 = ideal (x*y - x*z + z, x  - z, - x y*z + 2x  - 1)

o2 : Ideal of R1

If we want a Groebner basis of I1 with respect to lexicographic order we could substitute the ideal into a new ring with that order and compute directly,

i3 : R2 = QQ[x,y,z, MonomialOrder => Lex];

i4 : I2 = sub(I1, R2);

o4 : Ideal of R2

i5 : gens gb I2  -- performs computation in R2

o5 = | z6-z5-4z4-2z3+1 7y-4z5+5z4+13z3+10z2-6z-2 7x+4z5-5z4-13z3-10z2-z+2 |

              1       3
o5 : Matrix R2  <-- R2

but it may be faster to compute directly in the first order and then use FGLM.

i6 : G1 = gb I1;  -- performs computation in R1

i7 : gens fglm(G1, R2)

o7 = | z6-z5-4z4-2z3+1 7y-4z5+5z4+13z3+10z2-6z-2 7x+4z5-5z4-13z3-10z2-z+2 |

              1       3
o7 : Matrix R2  <-- R2

References

Further background and details can be found in the following resources:

Cox, Little, O'Shea - Using Algebraic Geometry (2005)
Faugere, Gianni, Lazard, Mora - Efficient Computation of Zero-dimensional Groebner Bases by Change of Ordering (1993)
Gerdt, Yanovich - Implementation of the FGLM Algorithm and Finding Roots of Polynomial Involutive Systems (2003)

Acknowledgement

The C++ implementation of the algorithms in Version 1.2.0 was sponsored by an IMA Coding Sprint at the Cornell University.

Caveat

The ideal generated by the Groebner basis must be zero-dimensional.

Authors

Version

This documentation describes version 1.1.0 of FGLM.

Source code

The source code from which this documentation is derived is in the file FGLM.m2.

Exports

Functions and commands
- fglm -- convert a Groebner basis
Methods
- fglm(GroebnerBasis,Ring) -- see fglm -- convert a Groebner basis
- fglm(Ideal,Ring) -- see fglm -- convert a Groebner basis

For the programmer

The object FGLM is a package.