# How to reproduce elimination_ideal with Giac ?

Hello,

I have the following parametric equations, where cost$=\cos t$, cos2t$=\cos 2t$, and $A^2+B^2=1$:  x = A*cost*cos2t - sint*sin2t, y = A*sint*cos2t + cost*sin2t, z = B*cos2t  I want to transform this system into an implicit equation with the help of Gröbner bases. In the Sage software, I do:

 R.<x, y, z, A, B, cost, sint, cos2t, sin2t> = PolynomialRing(QQ, 9); I = R.ideal([x - A*cost*cos2t + sint*sin2t, y - A*sint*cos2t - cost*sin2t, z - B*cos2t, A^2 + B^2 - 1, cost^2 + sint^2 - 1, cos2t - cost^2 + sint^2, sin2t - 2*sint*cost]); I.elimination_ideal([cost, sint, cos2t, sin2t]) 

Sage fastly returns three polynomials (including A^2+B^2-1).

Now I want to do it with Xcas/Giac (Xcas is the graphical interface to Giac). The Gröbner implicitization is not implemented, only Gröbner bases. So I request the Gröbner basis for:  x - A*cost*cos2t + sint*sin2t, y - A*sint*cos2t - cost*sin2t, z - B*cos2t, A^2 + B^2 - 1, cost^2 + sint^2 - 1, cos2t - cost^2 + sint^2, sin2t - 2*sint*cost  with the variables (the order is important) cost, sint, cos2t, sin2t, A, B, x, y, z.

That works for this example, i.e. I get a polynomial not involving cost and sint.

But now, if I replace cos2t with cos3t and sin2t with sin3t (and I adapt the trig identities), that does not work. I don't get any equation not involving cost and sint, except the trivial ones (A^2+B^2=1 and x^2+y^2+z^2=1).

So I'm wondering how Sage works, because it works in Sage. I have Cox & al's book but they don't explain how to proceed when there are relations among the variables (such as cos2t = cost^2 - sint^2, sin2t = 2*sint*cost) and constant parameters (A and B). What is the Gröbner basis I should request in order to get the same result as Sage, with which order among the variables and which order of the equations?

The Sage code for this second example is:

 R.<x, y, z, A, B, cost, sint, cos3t, sin3t> = PolynomialRing(QQ, 9); I = R.ideal([x - A*cost*cos3t + sint*sin3t, y - A*sint*cos3t - cost*sin3t, z - B*cos3t, A^2 + B^2 - 1, cost^2 + sint^2 - 1, cos3t - 4*cost^3+3*cost, sin3t - (4*cost^2-1)*sint]); I.elimination_ideal([cost, sint, cos3t, sin3t]) 

# Edit

The Giac code which does not work is:

 gbasis([x - a*cost*(4*cost^3-3*cost) + sint*(4*cost^2-1)*sint, y - a*sint*(4*cost^3-3*cost) - cost*(4*cost^2-1)*sint, z - b*(4*cost^3-3*cost), cost^2 + sint^2 - 1, a^2 + b^2 - 1], [cost, sint, x, y, z, a, b]) 

But if you replace a and b with numeric values, e.g. a=3/5 and b = 4/5, it works.

edit retag close merge delete

Can you add the code illustrating the problem in Giac? Also, did you check how does an equivalent code (without using elimination_ideal) in Sage work?

( 2023-07-24 18:36:31 +0100 )edit

@MaxAlekseyev I added the code in an edit. @rburing shows the equivalent Sage code, this is exactly what I do, up to the choice of the order.

( 2023-07-25 10:38:52 +0100 )edit
( 2023-07-29 11:07:48 +0100 )edit

Sort by » oldest newest most voted

I talked to a GIAC developer. The command to use is eliminate:

 eliminate([x - A*cost*cos2t + sint*sin2t, y - A*sint*cos2t - cost*sin2t, z - B*cos2t, A^2 + B^2 - 1, cost^2 + sint^2 - 1, cos2t - cost^2 + sint^2, sin2t - 2*sint*cost], [cost, sint, cos2t, sin2t])  The result is immediate.

He confirmed we should avoid the plex ordering.

more

You should specify not only an ordering of variables but a monomial ordering or term ordering. An algorithm for the elimination of variables is to choose an elimination ordering, where the variables-to-be-eliminated are greater than all the other variables, then compute a Groebner basis of the ideal with respect to this ordering, and finally select those elements who(se leading terms) do not involve the variables-to-be-eliminated.

In SageMath you would do this (more manually, without the elimination_ideal method) e.g. by:

sage: R.<cost, sint, cos3t, sin3t, x, y, z, A, B> = PolynomialRing(QQ, 9, order='degrevlex(4),degrevlex(5)')
sage: I = R.ideal([x - A*cost*cos2t + sint*sin2t, y - A*sint*cos2t - cost*sin2t, z - B*cos2t, A^2 + B^2 - 1, cost^2 + sint^2 - 1, cos2t - cost^2 + sint^2, sin2t - 2*sint*cost])
sage: [f for f in I.groebner_basis() if not any(v in f.lm().variables() for v in [cost,sint,cos2t,sin2t])]
[z^4*B^2 + 4*x*y^2*A*B^2 + x*z^2*A*B^2 - 2*z^4*A - 4*x*y^2*B^2 - x*z^2*B^2 + 3*z^2*A*B^2 - 2*z^4 - x*A*B^2 - 2*z^2*A + x*B^2 + A*B^2 + 2*z^2 - B^2,
x^2 + y^2 + z^2 - 1,
A^2 + B^2 - 1]


where the chosen monomial ordering degrevlex(4),degrevlex(5) is a block ordering with two blocks.

The giac documentation for gbasis suggests it is quite limited in its support for term orderings, so that you are forced to use lexicographic ordering (called plex in giac), which is an elimination ordering, but one that makes computations huge/slow:

0>> vars := [cost, sint, cos2t, sin2t, x, y, z, A, B];
[cost,sint,cos2t,sin2t,x,y,z,A,B]
// Time 0
1>> sys := [x - A*cost*cos2t + sint*sin2t, y - A*sint*cos2t - cost*sin2t, z - B*cos2t, A^2 + B^2 - 1, cost^2 + sint^2 - 1, cos2t - cost^2 + sint^2, sin2t - 2*sint*cost];
[x-A*cost*cos2t+sint*sin2t,y-A*sint*cos2t-cost*sin2t,z-B*cos2t,A^2+B^2-1,cost^2+sint^2-1,cos2t-cost^2+sint^2,sin2t-2*sint*cost]
// Time 0
2>> gbasis(sys,vars,plex)
...


It doesn't finish in reasonable time in giac 1.7.0. You can try a more recent version.

more

Thanks. I think there's a problem in the documentation in Giac: they say that plex is the default order, but when you don't specify which order you want you get something different. Indeed I crashed Giac with plex. I'm going to read your answer more carefully now. Thanks again.

( 2023-07-24 20:06:23 +0100 )edit

Also the strange with the cos3t example is that it works if I assign numerical values to A and B, otherwise it doesn't work.

( 2023-07-24 20:20:16 +0100 )edit