# GroebnerBasis internals and runtime dependence on variable list ordering

I have a problem I have reduced to asking for a Gröbner basis. For some reason, Mathematica is able to solve this in minutes, while other programs more dedicated to these types of calculations run for days (and counting).

Then I noticed something else strange. Reordering the variables in the variable list can have large effects on the Mathematica run time. My understanding is that for monomial ordering (by default it internally calculates with degree reverse lexicographical order), lexicographical refers to the alphabetical order of the variable names.

So I tried a simple experiment:

\$ math
Mathematica 12.0.0 Kernel for Linux x86 (64-bit)
Copyright 1988-2019 Wolfram Research, Inc.

In[1]:= constraints = {x^2 + y^2 + z^2 + x y z == 1, x^2 - 2 y z == 3};

In[2]:= GroebnerBasis[constraints, {x, y, z}] // InputForm

Out[2]//InputForm=
{4 + 4*y^2 + y^4 + 8*y*z + 4*y^3*z + 4*z^2 + 3*y^2*z^2 + 4*y*z^3 -
2*y^3*z^3 + z^4, -2*y - y^3 - 4*z + 2*x*z - 4*y^2*z - 2*y*z^2 - 2*z^3 +
x*z^3 + 2*y^2*z^3, 2 + y^2 + 2*y*z + x*y*z + z^2,
-4 + 2*x - 2*y^2 + x*y^2 - y*z - 2*z^2 + x*z^2 + 2*y^2*z^2, -3 + x^2 - 2*y*z}

In[3]:= GroebnerBasis[constraints, {z, x, y}] // InputForm

Out[3]//InputForm=
{9 - 6*x^2 + x^4 - 4*y^2 - 6*x*y^2 + 4*x^2*y^2 + 2*x^3*y^2 + 4*y^4,
3 - x^2 + 2*y*z, -2*y - 3*x*y + 2*x^2*y + x^3*y + 2*y^3 - 3*z + x^2*z,
-2 - 3*x + 2*x^2 + x^3 + 2*y^2 + 2*z^2}


So clearly I am wrong.
So probably my comparisons to other programs are not fair as well.

What is Mathematica doing internally?
And more specifically:

1. What is Mathematica doing so differently that I'm having trouble even getting another program to complete for comparison? It bothers me I cannot verify Mathematica's output, and the huge difference in run time has me worried. Especially given that the documentation makes it sounds like they use standard methods, and only calls out that by default it internally uses degree reverse lexicographic ordering as it is usually faster to calculate than straight lexicographical ordering -- but other programs use this same default for the same reason. I don't know what is going on.

2. How can I choose the ordering of the variables to "help" Mathematica? In particular I'm trying to prove the equations have no solution (hoping to get {1} as output), so should I try to arrange the variables likely closer related to the contradiction first? or last? or in the order I think they might be used to arrive at a contradiction?

3. Given all this, how can I ensure Mathematica uses the same ordering as another program for verification?

To be clear: the variable order in Mathematica can have a large effect (calculation taking ~ 40 minutes instead of ~ 4 minutes), but if it doesn't run out of memory it still completes (Mathematica can be a memory hog compared to the other programs). Versus the other programs still running after days. So monomial ordering cannot be the entire issue here. Internally Mathematica is doing something quite different, but it isn't called out in the documentation.

• tried using Sort -> True, MonomialOrder -> DegreeReverseLexicographic to see if Mathematica could figure out a good ordering for itself. However in my case its choice leads to it running out of memory instead of being able to complete the calculation. Feb 16 at 11:50
• Playing with some small examples, as far as I can tell, Macaulay2's GRevLex is the same as Mathematica's DegreeReverseLexicographic. If I explicitly tell Mathematica to use MonomialOrder -> DegreeReverseLexicographic, Method -> "Buchberger" these should be doing the same calculation. From my understanding of the documentation, the only difference of this from Method->"GroebnerWalk" is that it doesn't (by default) try to convert the answer to Lexicographic ordering afterwards. In other words with DegRevLex ordering, Buchberger should be same as GroebnerWalk? By speed this seems true. Feb 16 at 15:24

## 1 Answer

From the help of GroebnerBasis: "The Groebner basis in general depends on the ordering assigned to monomials. This ordering is affected by the ordering of the Subscript[x, i]." Therefore, there are 2 things to consider, the ordering of xi' s and the ordering of products of xi' s.

Considering the order of xi's, we print the xi's and the first Groebner basis function:

Do[{RotateRight[{x, y, z}, i],
GroebnerBasis[constraints, RotateRight[{x, y, z}, i]][[1]]} //
InputForm // Print, {i, 3}]

{{z, x, y}, 9 - 6*x^2 + x^4 - 4*y^2 - 6*x*y^2 + 4*x^2*y^2 + 2*x^3*y^2 + 4*y^4}

{{y, z, x}, 9 - 6*x^2 + x^4 - 4*z^2 - 6*x*z^2 + 4*x^2*z^2 + 2*x^3*z^2 + 4*z^4}

{{x, y, z}, 4 + 4*y^2 + y^4 + 8*y*z + 4*y^3*z + 4*z^2 + 3*y^2*z^2 + 4*y*z^3 - 2*y^3*z^3 + z^4}


The first Groebner basis function is a function of the two last xi'2 only. Therefore, the place a xi takes is determined by the position in the argument.

To my understanding, the ordering: Lexicographic,.. is used to determine which product of monomials is considered bigger. This ordering is used to determine basis.

• Ah, okay, that at least solves one puzzle. When I read the monomial order is affected by the variable ordering, I took it to mean it depended on the alphabetic ordering of the names of the x_i, due to my understanding of the term lexographic. But it takes lexographic to mean the order of the variables as given in the list. Feb 16 at 11:46
• So how do I ensure a problem I give to Mathematica, Macaulay2, and F5, are calculating the same thing? I can't figure out what Mathematica is doing differently that it can solve in 4 min what the others are taking days to look at. Feb 16 at 11:49
• I think you have to ask this at support@wolfram.com Feb 16 at 14:38