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 |
Further background and details can be found in the following resources:
The C++ implementation of the algorithms in Version 1.2.0 was sponsored by an IMA Coding Sprint at the Cornell University.
The ideal generated by the Groebner basis must be zero-dimensional.
This documentation describes version 1.1.0 of FGLM.
The source code from which this documentation is derived is in the file FGLM.m2.