New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Wrong groebner basis #11623

Open
Shekharrajak opened this Issue Sep 17, 2016 · 6 comments

Comments

Projects
None yet
3 participants
@Shekharrajak
Copy link
Member

Shekharrajak commented Sep 17, 2016

In [17]: from sympy.polys.polytools import groebner

In [18]: groebner([0.144*x*y+0.018*x**2+0.05*x-1.577,0.072*y**2+0.036*x*y+0.05*y-1.423], [x, y])
Out[18]: GroebnerBasis([1.0], x, y, domain=ℝ, order=lex)

But ans is :
-130.204 - 5.71425 *y**2 + 0.925926 *y**3 + y**4, 1.38889 + x + 3.73475* y - 0.281096* y**2 - 0.303584*y**3

@Shekharrajak

This comment has been minimized.

Copy link
Member

Shekharrajak commented Sep 17, 2016

But it works when we do

In [20]: groebner([(S(18)/125) *x*y + (S(18)/1000)*x**2+ (S(5)/100)*x - S(1577)/1000, (S(72)/1000)*y**2 + (S(36)/1000)*x*y + (S(5)/100)*y - S(1423)/1000], [x, y])
Out[20]: 
             ⎛⎡         3        2                          3          2          ⎤                           ⎞
             ⎜⎢    432⋅y    400⋅y    47831⋅y   25   4   25⋅y    22217⋅y    2024929⎥                           ⎟
GroebnerBasis⎜⎢x - ────── - ────── + ─────── + ──, y  + ───── - ──────── - ───────⎥, x, y, domain=ℚ, order=lex⎟
             ⎝⎣     1423     1423     12807    18         27      3888      15552 ⎦                           ⎠

I think it is solvable using solve_poly_system, but it is not working.

In [22]: solve_poly_system([0.144*x*y+0.018*x**2+0.05*x-1.577,0.072*y**2+0.036*x*y+0.05*y-1.423], [x, y])
#  None
@Shekharrajak

This comment has been minimized.

Copy link
Member

Shekharrajak commented Sep 17, 2016

In [1]: sys = [0.144*x*y+0.018*x**2+0.05*x-1.577,0.072*y**2+0.036*x*y+0.05*y-1.423]

In [2]: is_zero_dimensional(sys, [x, y])
Out[2]: False

I think this should be true. Ping @jksuom

@Shekharrajak Shekharrajak changed the title Wrond groebner basis Wrong groebner basis Sep 17, 2016

@jksuom

This comment has been minimized.

Copy link
Member

jksuom commented Sep 17, 2016

The theory of Gröbner bases assumes that the coefficient field will satisfy certain conditions (those of a 'computable field'). These conditions are not satisfied by floating point numbers, and that is why the computation fails.
I think the solution would be to replace all floats by rationals before the construction of a Gröbner basis in is_zero_dimensional.

@Shekharrajak

This comment has been minimized.

Copy link
Member

Shekharrajak commented Sep 17, 2016

So we should do this

In [29]:  groebner([nsimplify(0.144*x*y+0.018*x**2+0.05*x-1.577),nsimplify(0.072*y**2+0.036*x*y+0.05*y-1.423)], [x, y])
Out[29]: 
             ⎛⎡         3        2                          3          2          ⎤                           ⎞
             ⎜⎢    432⋅y    400⋅y    47831⋅y   25   4   25⋅y    22217⋅y    2024929⎥                           ⎟
GroebnerBasis⎜⎢x - ────── - ────── + ─────── + ──, y  + ───── - ──────── - ───────⎥, x, y, domain=ℚ, order=lex⎟
             ⎝⎣     1423     1423     12807    18         27      3888      15552 ⎦                           ⎠

It should be done internally right ?

@jksuom

This comment has been minimized.

Copy link
Member

jksuom commented Sep 17, 2016

That seems to be essentially what should be done in the function is_zero_dimensional before calling GroebnerBasis if there are floating point coefficients.

skirpichev added a commit to skirpichev/diofant that referenced this issue Sep 18, 2016

Stop groebner bases computation, if domain is not exact, like RR
In fact, RR is not even a field, but...

Conversion to Floats to Rationals seems to be even less
appropriate, than ebca09e.

Fixes sympy/sympy#11623

skirpichev added a commit to skirpichev/diofant that referenced this issue Sep 18, 2016

Stop groebner bases computation, if domain is not exact, like RR
In fact, RR is not even a field, but...

Conversion to Floats to Rationals seems to be even less
appropriate, than ebca09e.

Fixes sympy/sympy#11623
@KaoutharAarizou

This comment has been minimized.

Copy link

KaoutharAarizou commented Dec 20, 2018

Hello. I encountered the same problem when I tried to compute the grobner base from a set of polynomials written in cosine base.
The groebnerBase computation fails is even if I use sympy.nsimplify :

a0, a1, a2, t = sp.symbols('a0 a1 a2 t')

F1 = [p0, p1, p2, p3] = [sp.nsimplify( a0*(1/np.sqrt(3)) + a1*(np.sqrt(2)/np.sqrt(3))sp.cos(np.pi/6) + a2 (np.sqrt(2)/np.sqrt(3))sp.cos(np.pi/3) + 4), sp.nsimplify( a0(1/np.sqrt(3)) + a1(np.sqrt(2)/np.sqrt(3))sp.cos(np.pi/2) + a2(np.sqrt(2)/np.sqrt(3))sp.cos(np.pi)), sp.nsimplify( a0(1/np.sqrt(3)) + a1(np.sqrt(2)/np.sqrt(3))sp.cos((2t + 1)np.pi/6) + a2(np.sqrt(2)/np.sqrt(3))sp.cos((2t + 1)np.pi/3) + 6), sp.nsimplify( a0(1/np.sqrt(3)) + a1*(np.sqrt(2)/np.sqrt(3))sp.cos((2t + 3)np.pi/6) + a2(np.sqrt(2)/np.sqrt(3))sp.cos((2t + 3)*np.pi/3) -6) ]

Out[10]: GroebnerBasis([1.0], x, y, domain=ℝ, order=lex)

What's wrong ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment