Have you ever computed a Gröbner basis in some monomial order ≺₀ only to then realize that you actually wanted it in another order ≺₁? I know, happens all the time… But fret not, FGLM can convert between the two orders, and you don’t have to start your computation from scratch.

Here’s a recording where I’m explaining how FGLM works. If you’d like to look through the slides at your own pace, here they are. You can also find the two Gröbner bases used in the example as well as pseudocode for FGLM in the slides, in case you want to retrace the steps yourself.

If you are interested in not only how but also why FGLM works, have a look at the original publication. Section 5 and 6 give a comprehensive overview of FGLM’s complexity, which can be summarized as O(n·D³) where D is the dimension of quotient ring k[x₀, …, x_n-1] / <G> as a k-vector-space. More intuitively, D is the number of monomials in the staircase of a Gröbner basis, which are those dots in the non-blue region in this post’s first picture.