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

Question

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!

Answer 1

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$.

Answer 2

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.

Answer 3

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.