Solveset and Solver Discussion - sympy/sympy GitHub Wiki

Solveset and Solver Module

This wiki contains ideas to improve solveset and solver module.

Trigonometric Equation

I come across an idea (during discussion in google group ) that can solve the trigonometric equation g = 0 where g is a trigonometric polynomial. We can convert that into a polynomial system by expanding the sines and cosines in it, replacing sin(x) and cos(x) by two new variables s and c. before that need to check arguments are same or not.It should not be like sin(x) and cos(x**2). So now we have two variables and 1 equation another equation we know is :s2 + c2 − 1 = 0.Means sin(x)**2 + cos(x)**2 =1. Similarly we can solve others like tan,sec ; cot,cosec .But I think it will be better if we convert all the trigonometric functions into sin and cos ,and solve them for all cases .Then we don't need to add same types of codes. It needed another method solveset_trig which converts the trigonometric equation to sin, cos form , if it is not in this form.Then polynomial system replacing sin(x) and cos(x) by two new variables s and c.Then using linsolve we will get solution(s) returned, Now replacing s -> sin and c-> cos and then solveset_real can easily solve Eq(sin(x),) types of expressions. If we have equations like : sin(x)**3 + cos(3*x) = 0 then using fu module and trigsimp method we can get : s**3 + 4*(c**3) - 3*c =0 #(cos(3*x) expand) Similar things can be applied for hyperbolic functions. Failure case may occur when we have nested elements. and equations like :

1 − 2cosθ1 + 2cosθ2 − 2cosθ3 = −0.8
1 − 2cos(5*θ1) + 2cos(5*θ2) − 2cos(5*θ3) = 0
1 − 2cos(7*θ1) + 2cos(7*θ2) − 2cos(7*θ3) = 0

The main issues on trigonometric I found are https://github.com/sympy/sympy/issues/10217 and https://github.com/sympy/sympy/issues/9824 (nested expressions)

One of the good way may be using general function decomposition https://github.com/sympy/sympy/pull/9831

 >>> decompogen(sin(cos(x)), x)
[sin(x), cos(x)]
>>> decompogen(sin(x)**2 + sin(x) + 1, x)
[x**2 + x + 1, sin(x)]
>>> decompogen(sqrt(6*x**2 - 5), x)
[sqrt(x), 6*x**2 - 5]
>>> decompogen(sin(sqrt(cos(x**2 + 1))), x)
[sin(x), sqrt(x), cos(x), x**2 + 1]

so now we get the expressions in x and functions also.By solving these functions top to bottom recursively ,will lead to final result. This may solve all types of nested equations (right now solveset can't solve nested modulo/Trig equations properly ) problems. but to solve this

1 − 2cosθ1 + 2cosθ2 − 2cosθ3 = −0.8
1 − 2cos(5*θ1) + 2cos(5*θ2) − 2cos(5*θ3) = 0
1 − 2cos(7*θ1) + 2cos(7*θ2) − 2cos(7*θ3) = 0

there is need of function solver in solveset and improved decompogen to solve some complicated nested linear system ,equations and trigonometric equations.I found that docs have some examples to solve simple functions like:

>>> solve(f(x) - x, f(x))
[x]

but it can solve only simple equations.

>>> solve(Eq(-(f(x)**2 - 1)/f(x)**3,t - (x - 2)/x**2),f(x))
# take long long time

Issue: 7914 Solveset is not able to solve simple trigonometric equations like

eq = sin(2*x)*cos(x) + cos(2*x)*sin(x)-1
print solveset(eq,x, S.Reals)

Even it is not returning correct answer for : solveset(sin(3*x),x, S.Reals) types of simple equations.

This PR https://github.com/sympy/sympy/pull/10552 is returning

 >>> print solveset(sin(3*x)-1,x, S.Reals)
 ImageSet(Lambda(_n, 2*_n*pi - pi/2), Integers()) U ImageSet(Lambda(_n, 2*_n*pi + pi/6), Integers())
 U ImageSet(Lambda(_n, 2*_n*pi + 5*pi/6), Integers())

Answer seems correct, but I feel something better changes should be there. It gives correct answer for this type of equations also

  >>> print solveset(sin(pi*(x-5)/3),x,S.Reals)
  ImageSet(Lambda(_n, 3*(2*_n*pi - 2*pi/3)/(2*pi)), Integers())

solving this type of equation is easy with exp form that sympy do, but before rewriting them into exp form need better expression in sin, cos form so that sympy can handle exp form of this and return exact answer ,that is needed.

fu module have few basic formulas for trig equations.We can add many basic formulas in it .

There are many more trigonometric identitieslike

   >>> Sum(sin(n*pi/n), (n,1,m)).doit()
   0
   >>> product(sin(n*pi/n), (n,1,m)).doit()
    m
   0      #answer is pi/2
   >>> asin(x) + acos(x)
   acos(x) + asin(x)   # ans is pi/2

don't give correct answer.

11th revision addition: After some more research I found another good way to solve this:

1 − 2cosθ1 + 2cosθ2 − 2cosθ3 = −0.8
1 − 2cos(5*θ1) + 2cos(5*θ2) − 2cos(5*θ3) = 0
1 − 2cos(7*θ1) + 2cos(7*θ2) − 2cos(7*θ3) = 0

Replace/substitute θ1 to t1 and expand trig = true. Now all is in cos ,substitute cos(t1) to x , cos(t2) to y ,cos(t3) to z. collect the equation in (x,y,z) now it is non-linear equation system, that can be solved using solver.

     eq1=(1 - 2*cos(t1) + 2*cos(t2) - 2*cos(t3) + 0.8).expand(trig=True)
     eq2=(1 - 2*cos(5*t1) + 2*cos(5*t2) - 2*cos(5*t3) ).expand(trig=True)
     eq3=(1 - 2*cos(7*t1) + 2*cos(7*t2) - 2*cos(7*t3) ).expand(trig=True)

These step should be internal and return directly result.

Inverse Trigonometric Function

If solveset is able to solve all types of inverse trig equations then using this we may get a way to solve solveset(sin(3*x)-1,x, S.Reals) this types of problem without converting them into exp form. Using fu module we can convert Mul, divide sin ,cos equation to single argument then it's inverse may lead to proper answer.

>>> acos(S(1)/2)
pi/3
>>> asin(-S(1)/2)
-pi/6

so these should return general solution Some genral solutions

Simplified general form for Trigonometric solution

Right now Sympy returns not simplified general form.If you paste this solveset(cos(x) + cos(3*x) + cos(5*x),x) then you will get

ImageSet(Lambda(_n, 2*_n*pi + pi/2), Integers()) U ImageSet(Lambda(_n, 2*_n*pi - pi/2), Integers()) U ImageSet(Lambda(_n, 2*_n*pi - 2*pi/3), Integers()) U ImageSet(Lambda(_n, 2*_n*pi + 2*pi/3), Integers()) U ImageSet(Lambda(_n, 2*_n*pi - pi/3), Integers()) U ImageSet(Lambda(_n, 2*_n*pi + pi/3), Integers()) U ImageSet(Lambda(_n, 2*_n*pi - 5*pi/6), Integers()) U ImageSet(Lambda(_n, 2*_n*pi + 5*pi/6), Integers()) U ImageSet(Lambda(_n, 2*_n*pi - pi/6), Integers()) U ImageSet(Lambda(_n, 2*_n*pi + pi/6), Integers())

which can be simplified as (2*n +1)*pi/6, (2*n -1)*pi/6. Similarly many other solutions can be simplified. I found a solution for this after some discussion in Quora, thanks to active Mathematicians in Quora:

If we have terms like pi/6, pi/2, 5*pi/6, 7*pi/6, 3*pi/2. One way of approaching a sequence like this is this:

  • Take differences until the differences are all equal. In this case, the first differences are all pi/3. This indicates that you can fit a linear function in nn . If it had been necessary to calculate the second differences then one would have had to fit a quadratic function in nn . And so on. Very often one can calculate all possible differences without reaching equal differences. Then it's necessary to try something else.
  • Since a linear function will work fit a*n+b, where a and b are arbitrary constants. To do this, set: pi/6=a+b (using the first term) and pi/2=2*a+b (using the second term), then solve for a and b . Now you have a function that should represent all of the terms.

So actually we need a method that can make general from from the given terms. Some part of above steps,I tried to implement here : https://github.com/sympy/sympy/pull/10713

Right now Sympy

           >>> solveset(sin(x), x)
           {2⋅n⋅π | n ∊ ℤ} ∪ {2⋅n⋅π + π | n ∊ ℤ}

but this should be imageset(Lambda(n, n*pi), S.Integers)

I opened a PR https://github.com/sympy/sympy/pull/10552 which gives simplified answer for this simple equation, but not for all.It passes testcase .If we add above steps then it can returns simplified solution for all.

##Non linear system

I found that one of the good way may be substitution method (for simple cases ) and Using the Quadratic Formula ( some complicated cases ).

There are other ways also but to solve all types of Non linear system this method will be usefull and I have checked that many times we get multiple solution in non linear system and sympy is able to solve any type of equation that we get after the substitution.

Integer solution of a linear equation having two variables

Right now

  >>> print solveset(172*x + 20*y -1000,x, S.Integers)
  Intersection(Integers(), {-5*y/43 + 250/43})
  >>> print solve(172*x + 20*y -1000)
  [{x: -5*y/43 + 250/43}]

solve returns correct answer but if we want to get solution for S.Integers then need to shift to solveset. Integer solution is x = 8 + 22t and y = -1 - 5t solveset is defined to solve only for single variable, need extension here, so that we get solution for multiple variable also like solve. one good example is https://github.com/sympy/sympy/pull/1790

    >>> solve(x**y - 1)
    [{x: 1}, {y: 0}]

and then implement _ Diophantine equation_ algorithm to solve ax + by = c for integer solution of x,y. It is easy to implement as we have to find gcd(a,b) and n,m.Some good ways are in below links, I hope these can be converted into code with some good effort. After the discussion found that Diophantine is implemented in diophantine module but not connected with solveset. To connect these; solveset must be able to pass more than 1 variable for solution. Another thing is we can add Finiteset, ConditionSet, ImageSet they are not implemented in Diophantine.

Reference :

Inequalities

 >>> solveset(x**4 - 7*(x**2) + 4*x + 20 >=0,x ,S.Reals)
 (-∞, ∞)  # ans is 2
 >>> solve(x**4 - 7*(x**2) + 4*x + 20 >=0,x)
-∞ < x ∧ x < ∞   # ans is 2

I found this example here : http://www.cantab.net/users/henry.liu/inequalities.pdf In this link almost all the examples can't be done using sympy right now. Some main feature that can be added is : minimise, maximize etc. Reference : https://reference.wolfram.com/language/tutorial/MinimizationAndMaximization.html

Also there is need of checksol for inequalities also , so that we can directly check whether a number satisfies the inequality or not.

   >>> checksol( 2*(x-5) <= 4*x , x ,-5)
   raise TypeError("cannot determine truth value of Relational")
   TypeError: cannot determine truth value of Relational

more examples

Solving Transcendental Equations

Right now solver and solveset can't solve exponential and logarithm equations, like :

   >>> print solveset(5**(x**2) - 5**(6-x),x, S.Reals)
   ConditionSet(x, Eq(5**(x**2) - 5**(-x + 6), 0), (-oo, oo)

but it can easily solve x**2 - (6-x) equation so just need some work ,here. To solve more complicated equations like

  solveset(2**(4*y+1)- 3**(y),y, S.Reals)
  and 
  >>> solveset(log(10) + log(7-x) - log(x),x, S.Reals)
  {x | x ∊ ℝ ∧ -log(x) + log(-x + 7) + log(10) = 0}
  >>> solveset(log(10) + log(7-x) - log(x),x)
  {x | x ∊ ℂ ∧ -log(x) + log(-x + 7) + log(10) = 0}

need some change.It can solve these types of equations solveset(10**(5-x) - 8,x, S.Reals). More examples are here : http://tutorial.math.lamar.edu/Classes/Alg/SolveExpEqns.aspx

         >>> solveset(x**(2*a) + 2*(x**a) +1,x,S.Reals)
         ⎧             2⋅a      a        ⎫
         ⎨x | x ∊ ℂ ∧ x    + 2⋅x  + 1 = 0⎬
         ⎩                               ⎭
         >>> solve(x**(2*a) + 2*(x**a) +1,x)
         ⎡a ____⎤
         ⎣╲╱ -1 ⎦

Need to implement log,exp and Pow type equation solver efficiently.

      >>> solveset((x+log(x))**2 - 5*(x+log(x)) + 6 ,x)
     ⎧                               2                   ⎫
     ⎨x | x ∊ ℂ ∧ -5⋅x + (x + log(x))  - 5⋅log(x) + 6 = 0⎬
     ⎩                                                   ⎭

so solveset can't handle transcendental equation. So first need to implement transcendental equation solver in solveset.Then we can solve solveset(x+log(x)-3,x).

      >>> solveset(x+log(x)-3,x)
      {x | x ∊ ℂ ∧ x + log(x) - 3 = 0}

We can solve above problem by factorizing (x+log(x))**2 - 5*(x+log(x)).

We can't solve solveset(x+ log(x) -2,x), basically LambertW is not implemented. We need to rewrite _tsolve for solveset using bivariate.py.

Multivariate polynomial equations

If we have large expression ,that can be factorized then it should be better that, first we factorize the expression and then solve each factor. Some good algorithms I found are

If we can't factorize then one of the good way is Solving Symbolic Equations with PRESS .

Right now solveset can't solve multivariate polynomial equation system . For example :

I found a good way to solve these types of equations in this link (page 9 example 2.2) http://people.math.gatech.edu/~aleykin3/math4803spr13/BOOK/chapter1.pdf

So here we need to construct a Res(f1,f2 ) matrix.I hope this method will work for most of the equation. After the discussion I found that multivariate polynomial equation system can be solved using solve_poly_system in polysys.py so need to improve this method and implement in solveset.

As there is no issue in solve_poly_system so it is better to call the functions present in polysys.py inside the solveset and then convert the solution into the Set ,as solveset do.

Handling large expression and nested operation

Priority : low. sympy stuck when it get many symbols and operators in single expression during the execution.but works fine if we do this one by one means

        >>> a =10**10
        >>> a = a**10
        >>> a =a**10
        >>> print a

To solve this ,one of the good way can be using Expression tree . tree construction. More info

This can solve some issue for solvers because in some cases it stuck,it can't store/execute next line for these large expression.Another way can be split() which will split the express into token.

Previous discussion

Add a custom footer
⚠️ **GitHub.com Fallback** ⚠️