# How to speed up the process for calculating the Groebner basis?

I am currently trying to get the Groebner basis for 9 equations with 12 variables:

$$a_1^2+b_1^2+c_1^2+d_1^2-48.73=0\\ a_2^2+b_2^2+c_2^2+d_2^2-50.53=0\\ a_3^2+b_3^2+c_3^2+d_3^2-40.69=0\\ a_1a_2+b_1b_2+c_1c_2+d_1d_2-44.86=0\\ a_1a_3+b_1b_3+c_1c_3+d_1d_3-36.2=0\\ a_2a_3+b_2b_3+c_2c_3+d_2d_3-38.53=0\\ a_1b_2-a_2b_1+c_1d_2-c_2d_1+14.35=0\\ a_1b_3-a_3b_1+c_1d_3-c_3d_1+14.75=0\\ a_2b_3-a_3b_2+c_2d_3-c_3d_2+9.7=0$$

I know that $$a_1 = 1.5,a_2 = 1.0,a_3 = 4.0,b_1 = 2.4,b_2 = 3.5,b_3 = 3.1,c_1 = 3.4,c_2 = 5.2,c_3 = 3.2,d_1 = 5.4,d_2 = 3.2,d_3 = 2.2$$ is a solution for these equations. However, it's apparent that there will multiple solutions as there are more variables than equations. Therefore, I am trying the find the Groebner basis for these equations.

Up until now, I have tried to use the built-in functions in Mathematica and Maple to try to find the Groebner basis, but it takes hours to do the computation and still cannot give a result. The codes are as follows:

For Mathematica

    GroebnerBasis[{a1^2 + b1^2 + c1^2 + d1^2 - 48.73,
a2^2 + b2^2 + c2^2 + d2^2 - 50.53,
a3^3 + b3^2 + c3^2 + d3^2 - 40.69,
a1*a2 + b1*b2 + c1*c2 + d1*d2 - 44.86,
a3*a2 + b3*b2 + c3*c2 + d3*d2 - 38.53,
a1*a3 + b1*b3 + c1*c3 + d1*d3 - 36.2,
a1*b2 - a2*b1 + c1*d2 - c2*d1 + 14.35,
a3*b2 - a2*b3 + c3*d2 - c2*d3 - 9.7,
a1*b3 - a3*b1 + c1*d3 - c3*d1 + 14.75}, {a1, b1, c1, d1, a2, b2, c2,
d2, a3, b3, c3, d3}]


For Maple:

    with(Groebner);

G := [a1^2 + b1^2 + c1^2 + d1^2 - 48.73, a2^2 + b2^2 + c2^2 + d2^2 - 50.53, a3^3 + b3^2 + c3^2 + d3^2 - 40.69, a1*a2 + b1*b2 + c1*c2 + d1*d2 - 44.86, a3*a2 + b3*b2 + c3*c2 + d3*d2 - 38.53, a1*a3 + b1*b3 + c1*c3 + d1*d3 - 36.2, a1*b2 - a2*b1 + c1*d2 - c2*d1 + 14.35, a3*b2 - a2*b3 + c3*d2 - c2*d3 - 9.7, a1*b3 - a3*b1 + c1*d3 - c3*d1 + 14.75];

Basis(G, plex(a1, b1, c1, d1, a2, b2, c2, d2, a3, b3, c3, d3));


Could anyone give some suggestions on how to speed up the calculation or point out the mistakes I may miss? Thanks!

• The Buchberger algorithm has a few parameters you can throw into it. Usually the monomial ordering is the main one. If Mathematica / Maple doesn't let you modify that, you can probably find some alternative libraries that do. That said, I'm guessing this isn't considered an appropriate question for the forum. Oct 24, 2022 at 4:35
• Some relevant comments here: mathoverflow.net/questions/181350/… Oct 24, 2022 at 5:13
• Thanks, I will take a look at the comments. Oct 24, 2022 at 7:44
• The ordering of variables $a1,a2,a3,b1,b2,b3,c1,c2,c3,d1,d2,d3$ seems to be good. At least in Magma a Gröbner basis is computed in fractions of a second, once that order is given. Oct 24, 2022 at 10:27
• It might be faster to calculate Gröbner basis modulo primes and then go back to rational numbers . Try github.com/broune/mathicgb . Oct 24, 2022 at 19:00

In this case, because the equations have a lot of structure, you are better off using the structure than using a brute force tool such as Gröbner bases. (Unless this is just an exercise to help you learn about Gröbner bases.)

If you let $$M = \begin{pmatrix} a_1&a_2&a_3\\ b_1&b_2&b_3\\ c_1&c_2&c_3\\ d_1&a_d&d_3\end{pmatrix} \quad\text{and}\quad J = \begin{pmatrix} 0&1&0&0\\ -1&0&0&0\\ 0&0&0&1\\ 0&0&-1&0\end{pmatrix},$$ then your equations amount to $$M^\mathsf{T}M = S \quad\text{and}\quad M^\mathsf{T}JM = A,$$ where $$S$$ is a given symmetric $$3$$-by-$$3$$ matrix and $$A$$ is a given skewsymmetric $$3$$-by-$$3$$ matrix.

You have one solution $$M_0$$ to the above equations and you want to find all the others.

It's clear that, if you let $$\mathrm{U}(2)\subset\mathrm{GL}(4,\mathbb{R})$$ be the group of $$4$$-by-$$4$$ matrices $$R$$ that satisfy $$R^\mathsf{T}R = I_4$$ and $$R^\mathsf{T}JR = J$$, then any matrix of the form $$M = RM_0$$ for $$R\in \mathrm{U}(2)$$ will satisfy the above equations. Since $$\mathrm{U}(2)$$ is a group of dimension $$4$$, it follows that there will be a $$4$$-parameter family of solutions. (Note that this is one more than one would have expected from a naïve dimension count.)

Now, it's not hard to show that every solution $$M$$ is of the form $$RM_0$$ for some $$R\in\mathrm{U}(2)$$. The main point is to observe that every element of $$\mathrm{U}(2)$$ can be written uniquely in the form $$R = \begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0& \cos t& \sin t\\ 0&0& -\sin t& \cos t \end{pmatrix} \begin{pmatrix}x_0&x_1&x_2&x_3\\ -x_1&x_0&-x_3&x_2\\ -x_2&x_3&x_0&-x_1\\ -x_3&-x_2&x_1&x_0\end{pmatrix},$$ where $$x_0^2+x_1^2+x_2^2+x_3^2=1$$ and $$0\le t<2\pi$$. Using this, one can show that $$M_0$$ is $$\mathrm{U}(2)$$-equivalent to a solution with $$a_1>0$$ and $$b_1=c_1=d_1=0$$. (Just take $$(x_0,x_1,x_2,x_3)$$ to be a unit-sized positive multiple of $$(a_1,b_1,c_1,d_1)$$ in $$M_0$$) Using the equations, you now see that for that solution, you can solve uniquely for $$a_2$$, $$b_2$$, $$a_3$$, and $$b_3$$. Then you can use the remaining freedom of $$t$$ in the above formula to normalize $$d_2=0$$ and $$c_2>0$$. Then you can solve for $$c_2$$, $$c_3$$, and $$d_3$$. This shows that, taking $$R$$ in the above form, you can uniquely parametrize all solutions starting with $$M_0$$.

I am no expert in Groebner bases and can't give any insight as to why one method works and another doesn't. But using SAGE with the code

    K = QQ
R.<a1,b1,c1,d1,a2,b2,c2,d2,a3,b3,c3,d3> = PolynomialRing(K)
I = R.ideal(
a1^2 + b1^2 + c1^2 + d1^2 - K(4873/100),
a2^2 + b2^2 + c2^2 + d2^2 - K(5053/100),
a3^3 + b3^2 + c3^2 + d3^2 - K(4069/100),
a1*a2 + b1*b2 + c1*c2 + d1*d2 - K(4486/100),
a3*a2 + b3*b2 + c3*c2 + d3*d2 - K(3853/100),
a1*a3 + b1*b3 + c1*c3 + d1*d3 - K(362/10),
a1*b2 - a2*b1 + c1*d2 - c2*d1 + K(1435/100),
a3*b2 - a2*b3 + c3*d2 - c2*d3 - K(97/10),
a1*b3 - a3*b1 + c1*d3 - c3*d1 + K(1475/100)
)


produces a Groebner basis of 31 polynomials in under a minute. Presumably this is because we work over $$\mathbb{Q}$$.

Among these are four linear equations,

    a1 - 718731/1193537*a2 + 916810/1193537*b2 - 599813/1193537*a3 - 606825/1193537*b3,
b1 - 916810/1193537*a2 - 718731/1193537*b2 + 606825/1193537*a3 - 599813/1193537*b3,
c1 - 718731/1193537*c2 + 916810/1193537*d2 - 599813/1193537*c3 - 606825/1193537*d3,
d1 - 916810/1193537*c2 - 718731/1193537*d2 + 606825/1193537*c3 - 599813/1193537*d3


which determine $$(a_1, b_1, c_1, d_1)$$ from $$(a_2, b_2, c_2, d_2)$$ and $$(a_3, b_3, c_3, d_3)$$. I hope this is of some use.

• That's very helpful, I will try Sage ( and probably other tools) too. Oct 24, 2022 at 7:46
• Along similar lines, Mathematica may also do better if you apply Rationalize to the equations before trying to find the basis (or just enter the coefficients as, for example, 4873/100 rather than 48.73.) Oct 25, 2022 at 2:19
• Hello, I am still a little confused about the fact that there are 31 polynomials. Why working over ℚ will lead to such a result? Thanks! Oct 25, 2022 at 8:16
• And Rationalize does work very well. Thank you for your suggestion. Is this due to the faster computation speed when dealing with fractions？ Oct 25, 2022 at 8:23
• The code in this answer is missing the call to I.groebner_basis(). (And usually it's more useful to use I.minimal_associated_primes(), but that certainly doesn't finish in a minute). Oct 25, 2022 at 10:50

As suggested by Michael Seifert,

GroebnerBasis[Rationalize[{a1^2 + b1^2 + c1^2 + d1^2 - 48.73,
a2^2 + b2^2 + c2^2 + d2^2 - 50.53, a3^3 + b3^2 + c3^2 + d3^2 - 40.69,
a1*a2 + b1*b2 + c1*c2 + d1*d2 - 44.86, a3*a2 + b3*b2 + c3*c2 + d3*d2 - 38.53,
a1*a3 + b1*b3 + c1*c3 + d1*d3 - 36.2, a1*b2 - a2*b1 + c1*d2 - c2*d1 + 14.35,
a3*b2 - a2*b3 + c3*d2 - c2*d3 - 9.7, a1*b3 - a3*b1 + c1*d3 - c3*d1 + 14.75}, 0],
{a1, b1, c1, d1, a2, b2, c2, d2, a3, b3, c3, d3}]


produces the answer (on demand through Dropbox) in two minutes.