python - To solve a set of many algebraic equations with more unknowns under a restrictive domain - Stack Overflow

admin管理员组

文章数量:1356232

I have recently tried to solve (for some nontrivial solutions) a set of 15 nonlinear algebraic equations with 18 unknowns (each of which is -1, -1/2, 0, 1/2, or 1) by using "nonlinsolve" of sympy in Python, and the following was a simple attempt:

from sympy import symbols, nonlinsolve, Interval
from sympy import FiniteSet

x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18 = symbols('x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18', real=True)
domains = [FiniteSet(-1,-1/2, 0, 1/2, 1),FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1)]
vars = [x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18]
eqn1 = x1*x1 - x10*x10 + x4*x4 - x13*x13 + x7*x7 - x16*x16 - 1
eqn2 = x1*x2 - x10*x11 + x4*x5 - x13*x14 + x7*x8 - x16*x17
eqn3 = x1*x3 - x10*x12 + x4*x6 - x13*x15 + x7*x9 - x16*x18
eqn4 = x2*x1 - x11*x10 + x5*x4 - x14*x13 + x8*x7 - x17*x16
eqn5 = x2*x2 - x11*x11 + x5*x5 - x14*x14 + x8*x8 - x17*x17 - 0.5
eqn6 = x2*x3 - x11*x12 + x5*x6 - x14*x15 + x8*x9 - x17*x18
eqn7 = x3*x1 - x12*x10 + x6*x4 - x15*x13 + x9*x7 - x18*x16
eqn8 = x3*x2 - x12*x11 + x6*x5 - x15*x14 + x9*x8 - x18*x17
eqn9 = x3*x3 - x12*x12 + x6*x6 - x15*x15 + x9*x9 - x18*x18
eqn10 = x1*x11 - x10*x2 + x4*x14 - x13*x5 + x7*x17 - x16*x8
eqn11 = x1*x12 - x10*x3 + x4*x15 - x13*x6 + x7*x18 - x16*x9
eqn12 = x2*x10 - x11*x1 + x5*x13 - x14*x4 + x8*x16 - x17*x7
eqn13 = x2*x12 - x11*x3 + x5*x15 - x14*x6 + x8*x18 - x17*x9
eqn14 = x3*x10 - x12*x1 + x6*x13 - x15*x4 + x9*x16 - x18*x7
eqn15 = x3*x11 - x12*x2 + x6*x14 - x15*x5 + x9*x17 - x18*x8
system = [eqn1,eqn2,eqn3,eqn4,eqn5,eqn6,eqn7,eqn8,eqn9,eqn10,eqn11,eqn12,eqn13,eqn14,eqn15]
nonlinsolve(system,vars)

On the other hand, the python in my computer appears not able to properly finish the solving equations, taking long time without any result after running the code in the program.

Although there are many equations and more unknowns, I expected that it might not give too much burden for computations because the domain for solutions is quite restrictive, only having 5 elements, -1, -1/2, 0, 1/2, and 1; if there might be some way(s) to correct the code or to try alternative(s) for solving such kind of a set of many algebraic equations with more unknowns it would be useful for my reference.

Also to avoid too many trivial solutions, I may impose a bit more conditions upon the 18 unknowns that

x1**2 + x2**2 + x3**2, x4**2 + x5**2 + x6**2, x7**2 + x8**2 + x9**2, x10**2 + x11**2 + x12**2, x13**2 + x14**2 + x15**2, x16**2 + x17**2 + x18**2

These 6 pairs are not zeros.

I have recently tried to solve (for some nontrivial solutions) a set of 15 nonlinear algebraic equations with 18 unknowns (each of which is -1, -1/2, 0, 1/2, or 1) by using "nonlinsolve" of sympy in Python, and the following was a simple attempt:

from sympy import symbols, nonlinsolve, Interval
from sympy import FiniteSet

x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18 = symbols('x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18', real=True)
domains = [FiniteSet(-1,-1/2, 0, 1/2, 1),FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1), FiniteSet(-1,-1/2, 0, 1/2, 1)]
vars = [x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18]
eqn1 = x1*x1 - x10*x10 + x4*x4 - x13*x13 + x7*x7 - x16*x16 - 1
eqn2 = x1*x2 - x10*x11 + x4*x5 - x13*x14 + x7*x8 - x16*x17
eqn3 = x1*x3 - x10*x12 + x4*x6 - x13*x15 + x7*x9 - x16*x18
eqn4 = x2*x1 - x11*x10 + x5*x4 - x14*x13 + x8*x7 - x17*x16
eqn5 = x2*x2 - x11*x11 + x5*x5 - x14*x14 + x8*x8 - x17*x17 - 0.5
eqn6 = x2*x3 - x11*x12 + x5*x6 - x14*x15 + x8*x9 - x17*x18
eqn7 = x3*x1 - x12*x10 + x6*x4 - x15*x13 + x9*x7 - x18*x16
eqn8 = x3*x2 - x12*x11 + x6*x5 - x15*x14 + x9*x8 - x18*x17
eqn9 = x3*x3 - x12*x12 + x6*x6 - x15*x15 + x9*x9 - x18*x18
eqn10 = x1*x11 - x10*x2 + x4*x14 - x13*x5 + x7*x17 - x16*x8
eqn11 = x1*x12 - x10*x3 + x4*x15 - x13*x6 + x7*x18 - x16*x9
eqn12 = x2*x10 - x11*x1 + x5*x13 - x14*x4 + x8*x16 - x17*x7
eqn13 = x2*x12 - x11*x3 + x5*x15 - x14*x6 + x8*x18 - x17*x9
eqn14 = x3*x10 - x12*x1 + x6*x13 - x15*x4 + x9*x16 - x18*x7
eqn15 = x3*x11 - x12*x2 + x6*x14 - x15*x5 + x9*x17 - x18*x8
system = [eqn1,eqn2,eqn3,eqn4,eqn5,eqn6,eqn7,eqn8,eqn9,eqn10,eqn11,eqn12,eqn13,eqn14,eqn15]
nonlinsolve(system,vars)

On the other hand, the python in my computer appears not able to properly finish the solving equations, taking long time without any result after running the code in the program.

Although there are many equations and more unknowns, I expected that it might not give too much burden for computations because the domain for solutions is quite restrictive, only having 5 elements, -1, -1/2, 0, 1/2, and 1; if there might be some way(s) to correct the code or to try alternative(s) for solving such kind of a set of many algebraic equations with more unknowns it would be useful for my reference.

Also to avoid too many trivial solutions, I may impose a bit more conditions upon the 18 unknowns that

x1**2 + x2**2 + x3**2, x4**2 + x5**2 + x6**2, x7**2 + x8**2 + x9**2, x10**2 + x11**2 + x12**2, x13**2 + x14**2 + x15**2, x16**2 + x17**2 + x18**2

These 6 pairs are not zeros.

• python
• sympy

Share Improve this question Follow edited Mar 30 at 0:28 rooted-and-grounded asked Mar 29 at 18:19 rooted-and-groundedrooted-and-grounded 111 bronze badge 9

• 1 You create eqnXX, but your system has eqsXX and eqaXX. What would the "solution" to this be? Each of the 387 million combinations of values produces a result. What do you want to solve for? Minimums? Zeros? – Tim Roberts Commented Mar 29 at 18:32
• You are right; thank you for kind comment, and I could try to revise it properly. For this system, I am considering to find such 18 unknowns to make the equations simultaneously zeros under a restriction that such roots are found among only -1, 0, or 1. – rooted-and-grounded Commented Mar 29 at 22:35
• Well, obviously they cannot ALL be zero; eqn5 can never be zero because of the -0.5. If x1 is 1 and the rest are 0, they will all be zero except eqn5, which will be -0.5. That's probably the minimum. – Tim Roberts Commented Mar 29 at 22:39
• Yes, you are right; I am sorry for the mistake, and a bit more revised it under a less restrictive condition, "such roots are to be found among only -1, -1/2, 0, 1/2, or 1." Thank you for kind correction, and what I endeavour to do is to find some sets of nontrivial solutions which may be as simple as possible. – rooted-and-grounded Commented Mar 29 at 22:48
• Now there are 4 trillion possible combinations, and I'm not sure there is any way to solve it without trying each one. However, if x1=1, x5=x8=0.5 and the rest are 0, then all equations are 0. That's not the only solution. – Tim Roberts Commented Mar 29 at 22:55

 |  Show 4 more comments

1 Answer 1

Sorted by: Reset to default 0

I would recommend handling this with python-constraint:

X,Y,Z=(1,10,4,13,7,16),(2,11,5,14,8,17),(3,12,6,15,9,18)
def twiddle(a,b,c,d,e,f):
    return b,a,d,c,f,e

def v(*i):
    return tuple(['x'+str(i) for i in i])

from constraint import *
problem=Problem()
for i in range(1,19):
    problem.addVariable('x'+str(i),[-1,-.5,0,.5,1])

l = lambda a,b,c,d,e,f,A,B,C,D,E,F: a*A-b*B+c*C-d*D+e*E-f*F==0
problem.addConstraint(lambda a,b,c,d,e,f,A,B,C,D,E,F: a*A-b*B+c*C-d*D+e*E-f*F==1,v(*X,*X))
problem.addConstraint(l,v(*X,*Y))
problem.addConstraint(l,v(*X,*Z))
problem.addConstraint(lambda a,b,c,d,e,f,A,B,C,D,E,F: a*A-b*B+c*C-d*D+e*E-f*F==.5,v(*Y,*X))
problem.addConstraint(l,v(*Y,*Y))
problem.addConstraint(l,v(*Y,*Z))
problem.addConstraint(l,v(*Z,*X))
problem.addConstraint(l,v(*Z,*Y))
problem.addConstraint(l,v(*Z,*Z))
problem.addConstraint(l,v(*X,*twiddle(*Y)))
problem.addConstraint(l,v(*X,*twiddle(*Z)))
problem.addConstraint(l,v(*Y,*twiddle(*X)))
problem.addConstraint(l,v(*Y,*twiddle(*Z)))
problem.addConstraint(l,v(*Z,*twiddle(*X)))
problem.addConstraint(l,v(*Z,*twiddle(*Y)))

>>> sol=problem.getSolutionIter()
>>> next(sol)
...waiting...

本文标签：