3
$\begingroup$

Consider the following system of equations:

$$ \begin{cases} d_0^2+d_1^2=2 \\ d_0 d_1 = -1 \end{cases} $$

Here's Mathematica solving it and producing the Gröbner Basis:

equations = {
    d0^2+d1^2 == 2,
    d0 d1 == -1
};

Solve[equations]
GroebnerBasis[equations,{d0,d1}]

{{d0->-1, d1->1}, {d0->1, d1->-1}}
{1 - 2 d1^2 + d1^4, d0 + 2 d1 - d1^3}

However, we can double the second equation and add to the first obtaining $d_0^2 + 2 d_0d_1 + d_1^2=0$ which is equivalent to $(d_0+d_1)^2=0$ or simply $d_0+d_1=0$.

If we add that equation, it shouldn't change the solutions and it doesn't. However, it does change (and simplify) the Gröbner basis.

moarEquations = Append[equations, d0+d1==0];
Solve[moarEquations]
GroebnerBasis[moarEquations,{d0,d1}]

{{d0->-1,d1->1}, {d0->1,d1->-1}}
{-1+d1^2, d0+d1}

Can I somehow tell Mathematica to end up with the simpler basis? For larger systems it also impacts the computation speed a lot (i.e. adding one more equation reduces Solve and GroebnerBasis time).

$\endgroup$
  • $\begingroup$ Have you looked into what happens if you change the MonomialOrder setting? $\endgroup$ – J. M. will be back soon Mar 3 at 13:01
  • $\begingroup$ I inserted the initial system in a quote because I was getting the Your post appears to contain code that is not properly formatted as code. error otherwise. Help appreciated. $\endgroup$ – Džuris Mar 3 at 13:01
  • $\begingroup$ @J.M.iscomputer-less yeah, but the provided options doesn't make it simpler (some make the basis more complicated). Maybe there's a clever custom ordering, but I don't know how to come up with such myself. $\endgroup$ – Džuris Mar 3 at 13:05
  • 2
    $\begingroup$ The two bases do not generate the same ideal, so there's no way to get the first GroebnerBasis[] call to return the output of the second. What's needed is something like computing the radical of the ideal. If I understood correctly, this is essentially what Reduce is doing under the hood using cylindrical algebraic decomposition to solve the equations. In other words, what you're asking to do at the user level is what is being done internally. @DanielLichtblau, if he sees this, can comment more authoritatively and accurately. $\endgroup$ – Michael E2 Mar 3 at 14:40
  • 2
    $\begingroup$ It's pretty much as @MichaelE2 stated (except I think Reduce is using factoring of the basis rather than CAD). One can do similarly by taking the original GB, factoring each polynomial (FactorSquareFree will suffice here), and removing the exponents of each factor. This is an after-the-fact (of computing the GB) approach so it will not improve speed. If you happen to know in advance what powers might be present, adding their reduced counterparts to the input will help. $\endgroup$ – Daniel Lichtblau Mar 3 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.