Implementing transolve in solveset

Yathartha Joshi edited this page Mar 19, 2018 · 6 revisions

How old solve solves transcendental equations.

The way solve handles equations is quite heuristic. It tries all possible form for the equation and then when it gets the desired form it returns the result. This becomes inefficient as lot of time is wasted during the function call.

First _solve tries to solve using solve_linear, then tries to solve by converting to polynomial and if still not get the result, tries to look for radicals and remove it, and then tries _tsolve as the last option.

_tsolve tries to get the result by inverting (_invert) and tries to find a pattern of the equation, if unsuccessful, checks if it is bivariate (_solve_lambert), if still not found tries posifying the result as the last option.

Disadvantages in solve and _tsolve

  • It gets into a lot of function calls, thereby increasing computing.

    >>> f = 5**(x-3) - 3**(2*x + 1)
    >>> solve(f, x)
    [-log(375)/(-log(5) + 2*log(3))]
    --- 0.5069870948791504 seconds ---
    
    >>> solveset(f, x, S.Reals)
    {-log(375)/(-log(5) + 2*log(3))}            
    --- 0.1461641788482666 seconds ---    # in accordance with what is implemented in #13045
    
    
  • Also _tsolve does not return complex solutions.

    >>> solveset(f, x)
    ImageSet(Lambda(_n, (2*_n*I*pi + log(375))/(-2*log(3) + log(5))), S.Integers)
    

More modular transcendental equation solver for solveset

  • Exponential equations

    Exponential equation are not handled due to the fact that ther is no proper simplification to a more general form. One heuristic way can be modifying the _invert_real and _invet_complex for genral types of exponential equations a*f(x) + b*g(x) where f(x) and g(x) are power functions. This has been implemented in #13045

  • Logarithmic Equations

    These equations can be solved by using logcombine, it will simplify log equations by using logarithmic properties to an extent where it can be solved by inverting. Implemented in #13045

  • Equations solvable by LambertW function

    How _tsolve solves?

    It uses _solve_lambert to solve lambert equations. Eqs solvable by LambertW follows f(x, a..f) = a*log(b*X + c) + d*X - f = 0 general form, _solve_lambert describes few forms for f(x, a..f). eqs are identified as these forms and are converted to the general form (f(x, a..f)) so that it can be easily solved by _lambert.

    Limitations:

    • Solutions are only in real domain.

      >>> f = x**3 - 3**x
      >>> solve(f, x)
      # only real solutions
      [-3*LambertW(-log(3)/3)/log(3), -3*LambertW(-log(3)/3, -1)/log(3)]
      
      f has two solutions in complex domain as well
      
        - [-3*LambertW(1/6*(1-I*sqrt(3))log(3))/log(3)]
      
        - [-3*LambertW(1/6*(1+I*sqrt(3))log(3))/log(3)]
      
      

    Solving lambert in transolve:

    def _lambert(f, symbol, domain, **flags):
        if flags.pop('bivariate', True):
            try:
                # convert it into polynomial for _solve_lambert
                poly.as_poly()
                g = _filtered_gens(poly, symbol)
                result = _solve_lambert(f, symbol, g)
                return FiniteSet(result)
            except NotImplementedError:
                # check if it is bivarate
                if (g == 2):
                   try:
                       gpu = bivariate_type(f, *g)
                       if gpu is None:
                           raise NotImplementedError
                       g, p, u = gpu
                       flags['bivariate'] = False
    
                       # need to make transolve more powerful for getting such type of solutions
                       inv = transolve(g - u, symbol, domain, **flags)
                    
                       if inv:
                           solution = _solveset(p, u, domain, _check=True)
                           # replace the `u` variable in solution with inv values.
                           return FiniteSet([i.subs(u, s) for i in inv for s in solution])
                   except NotImplementedError:
                       raise NotImplementedError
         raise NotImplementedError
  • Trignometric Equations

    • Incorporating solve_decomposition for solving polynomial type trignometric equations.

    • Improving the set infrastructure (possibly union of imagesets)

    There are lots of trignometric equations that needs to be taken care of, refer: [#12340] (https://github.com/sympy/sympy/issues/12340)

    Nested type equations can be solved using solve_decomposition

    eg: cos((sin(x)+1))-1 issue#10217. equations that remain unsolvable by _solve_trig should be pass into solve_decomposition (as a last resort). Even equations f = sin(3*x) needs simplification

    >>> f = sin(3*x)
    >>> solveset(f, x, S.Reals)
    Union(ImageSet(Lambda(_n, 2*_n*pi), S.Integers), ImageSet(Lambda(_n, 2*_n*pi + pi), S.Integers), 
    ImageSet(Lambda(_n, 2*_n*pi + 4*pi/3), S.Integers), ImageSet(Lambda(_n, 2*_n*pi + 2*pi/3), S.Integers), 
    ImageSet(Lambda(_n, 2*_n*pi + 5*pi/3), S.Integers), ImageSet(Lambda(_n, 2*_n*pi + pi/3), S.Integers))
    >>> solve_decomposition(f, x, S.Reals)
    ⎧2⋅n⋅π        ⎫   ⎧2⋅n⋅π   π        ⎫
    ⎨───── | n ∊ ℤ⎬ ∪ ⎨───── + ─ | n ∊ ℤ⎬
    ⎩  3          ⎭   ⎩  3     3        ⎭
    
    

    Equations of type sin(2*x) + sin(4*x) + sin(6*x) needs to improve their result, this will probably achieved by the unification of imagesets.

One way to solve most of the trigonometric equations is to implement different helpers where each helper has its own heuristics and it tries to find out the best solution. We can probably use fu module for some equations to get simplified result and solve it.

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.