Ask Your Question
1

How do I use Groebner's basis in SageMath to solve a nonlinear system? [closed]

asked 2021-08-14 10:56:45 +0200

Periodic_1_6 gravatar image

updated 2023-05-19 21:57:50 +0200

FrédéricC gravatar image

How do I use Groebner's basis in SageMath to solve a nonlinear system? kindly someone give me an example with this non linear system?

var('N A y a B b C c D d w V v Z z U u')

eq0 = N-4899 == 0

eq1 = (-2 + sqrt(N + (1 - 2*y)^2))/4-A == 0
eq2 = 4*A+1-2*(y-1)-a == 0
eq3 = 8*(A-1)*a-(N-36)-(a-6)^2  == 0
eq4 = ((a-7)-2*(B-1))*((a-5)-2*(B-1))+1-(b-6)^2  == 0
eq5 = ((b-7)-2*(C-1))*((b-5)-2*(C-1))+1-(c-6)^2  == 0
eq6 = ((c-7)-2*(D-1))*((c-5)-2*(D-1))+1-(d-6)^2  == 0
eq7 = 8*(B-1)*a-(a-6)^2+36-(16*B*(B+1)+3) == 0
eq8 = 8*(C-1)*b-(b-6)^2+36-(16*C*(C+1)+3) == 0
eq9 = 8*(D-1)*c-(c-6)^2+36-(16*D*(D+1)+3) == 0
eq10= d-13 == 0

eq11= 8*(A-1)*(4*A+1)-(16*A*(A+1)+3-36)-(w-6)^2 == 0
eq12= ((w-7)-2*(V-1))*((w-5)-2*(V-1))+1-(v-6)^2  == 0
eq13= ((v-7)-2*(Z-1))*((v-5)-2*(Z-1))+1-(z-6)^2  == 0
eq14= ((z-7)-2*(U-1))*((z-5)-2*(U-1))+1-(u-6)^2  == 0
eq15= 8*(V-1)*w-(w-6)^2+36-(16*V*(V+1)+3) == 0
eq16= 8*(Z-1)*v-(v-6)^2+36-(16*Z*(Z+1)+3) == 0
eq17= 8*(U-1)*z-(z-6)^2+36-(16*U*(U+1)+3) == 0
eq18 = u-13 == 0

solutions = solve([eq0,eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9,eq10,eq11,eq12,eq13,eq14,eq15,eq16,eq17,eq18],N,A,y,a,B,b,C,c,D,d,w,V,v,Z,z,U,u)
sol = solutions 
print(sol)
edit retag flag offensive reopen merge delete

Closed for the following reason the question is answered, right answer was accepted by Periodic_1_6
close date 2021-08-18 08:35:25.100894

1 Answer

Sort by » oldest newest most voted
4

answered 2021-08-17 17:29:58 +0200

Max Alekseyev gravatar image

First off, Grobner basis approach can work only for polynomial equations, while your eq1 is not such. Luckily, it can be converted into a polynomial one: (N + (1 - 2*y)^2)) - (4*A+2)^2 == 0.

When all equations are polynomial, we can define a polynomial ring and compute all solutions as the variety of the ideal generated by the polynomials (lhs) from the given equations:

R.<N,A,y,a,B,b,C,c,D,d,w,V,v,Z,z,U,u> = PolynomialRing(QQ)
eq = [ N-4899,
    (N + (1 - 2*y)^2) - (4*A+2)^2,
    4*A+1-2*(y-1)-a,
    8*(A-1)*a-(N-36)-(a-6)^2,
    ((a-7)-2*(B-1))*((a-5)-2*(B-1))+1-(b-6)^2,
    ((b-7)-2*(C-1))*((b-5)-2*(C-1))+1-(c-6)^2,
    ((c-7)-2*(D-1))*((c-5)-2*(D-1))+1-(d-6)^2,
    8*(B-1)*a-(a-6)^2+36-(16*B*(B+1)+3),
    8*(C-1)*b-(b-6)^2+36-(16*C*(C+1)+3),
    8*(D-1)*c-(c-6)^2+36-(16*D*(D+1)+3),
    d-13,
    8*(A-1)*(4*A+1)-(16*A*(A+1)+3-36)-(w-6)^2,
    ((w-7)-2*(V-1))*((w-5)-2*(V-1))+1-(v-6)^2,
    ((v-7)-2*(Z-1))*((v-5)-2*(Z-1))+1-(z-6)^2,
    ((z-7)-2*(U-1))*((z-5)-2*(U-1))+1-(u-6)^2,
    8*(V-1)*w-(w-6)^2+36-(16*V*(V+1)+3),
    8*(Z-1)*v-(v-6)^2+36-(16*Z*(Z+1)+3),
    8*(U-1)*z-(z-6)^2+36-(16*U*(U+1)+3),
    u-13]
J = R.ideal(eq)
print( J.variety() )

which gives us the following 32 solutions:

[{u: 13, U: 5, z: 21, Z: 9, v: 37, V: 17, w: 69, d: 13, D: 5, c: 21, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: 9, v: 37, V: 17, w: 69, d: 13, D: 5, c: 21, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: 9, v: 37, V: 17, w: 69, d: 13, D: -3, c: -9, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: 9, v: 37, V: 17, w: 69, d: 13, D: -3, c: -9, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: 9, v: 37, V: -15, w: -57, d: 13, D: 5, c: 21, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: 9, v: 37, V: -15, w: -57, d: 13, D: 5, c: 21, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: 9, v: 37, V: -15, w: -57, d: 13, D: -3, c: -9, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: 9, v: 37, V: -15, w: -57, d: 13, D: -3, c: -9, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: -7, v: -25, V: 17, w: 69, d: 13, D: 5, c: 21, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: -7, v: -25, V: 17, w: 69, d: 13, D: 5, c: 21, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: -7, v: -25, V: 17, w: 69, d: 13, D: -3, c: -9, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: -7, v: -25, V: 17, w: 69, d: 13, D: -3, c: -9, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: -7, v: -25, V: -15, w: -57, d: 13, D: 5, c: 21, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: -7, v: -25, V: -15, w: -57, d: 13, D: 5, c: 21, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: -7, v: -25, V: -15, w: -57, d: 13, D: -3, c: -9, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: 5, z: 21, Z: -7, v: -25, V: -15, w: -57, d: 13, D: -3, c: -9, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: 9, v: 37, V: 17, w: 69, d: 13, D: 5, c: 21, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: 9, v: 37, V: 17, w: 69, d: 13, D: 5, c: 21, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: 9, v: 37, V: 17, w: 69, d: 13, D: -3, c: -9, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: 9, v: 37, V: 17, w: 69, d: 13, D: -3, c: -9, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: 9, v: 37, V: -15, w: -57, d: 13, D: 5, c: 21, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: 9, v: 37, V: -15, w: -57, d: 13, D: 5, c: 21, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: 9, v: 37, V: -15, w: -57, d: 13, D: -3, c: -9, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: 9, v: 37, V: -15, w: -57, d: 13, D: -3, c: -9, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: -7, v: -25, V: 17, w: 69, d: 13, D: 5, c: 21, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: -7, v: -25, V: 17, w: 69, d: 13, D: 5, c: 21, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: -7, v: -25, V: 17, w: 69, d: 13, D: -3, c: -9, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: -7, v: -25, V: 17, w: 69, d: 13, D: -3, c: -9, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: -7, v: -25, V: -15, w: -57, d: 13, D: 5, c: 21, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: -7, v: -25, V: -15, w: -57, d: 13, D: 5, c: 21, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: -7, v: -25, V: -15, w: -57, d: 13, D: -3, c: -9, C: 9, b: 37, B: 17, a: 69, y: 1, A: 17, N: 4899},
 {u: 13, U: -3, z: -9, Z: -7, v: -25, V: -15, w: -57, d: 13, D: -3, c: -9, C: -7, b: -25, B: 17, a: 69, y: 1, A: 17, N: 4899}]
edit flag offensive delete link more

Comments

@Max Alekseyev forgive my ignorance. If I may, one last question: what is the computational complexity, using this method, to solve this system?

Periodic_1_6 gravatar imagePeriodic_1_6 ( 2021-08-17 22:05:46 +0200 )edit

Computing Grobner basis is computationally expensive. For your system, it took a couple of hours to compute solutions.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-08-17 22:26:46 +0200 )edit

thank you @Max Alekseyev

Periodic_1_6 gravatar imagePeriodic_1_6 ( 2021-08-18 08:34:27 +0200 )edit

Question Tools

1 follower

Stats

Asked: 2021-08-14 10:56:45 +0200

Seen: 426 times

Last updated: Aug 17 '21