GSoC 2017 Yathartha Anirudh Joshi Application: Solvers: Extending Solveset II - sympy/sympy GitHub Wiki

Table of Contents

About Me

Basic Information

Name: Yathartha Anirudh Joshi

Email: [email protected], [email protected]

University: B.T.K.I.T, Dwarahat(Uttarakhand Technical University)

Github/IRC: Yathartha22

Blog: https://yaj22.wordpress.com

Time Zone: IST (UTC +5:30)

Personal Background

I am 3rd year undergraduate pursuing Bachelor of Technology in Computer Science and Engineering at B.T.K.I.T, Dwarahat, Uttarakhand, India. I love Mathematics and the logic that resides in it. I enjoy problem solving and always try to get the best and efficient solution to the problem.

Programming Details

I work on Ubuntu 16.04 and Windows operating system with Sublime Text 3 as my primary editor. It's been about more than two year since I started competitive coding. I began coding with C++ and C. I like these languages because of their simplicity and also because I had C++ in my intermediate. Implementation of what we think becomes an easy task in C/C++. I am comfortable with STL and algorithms. I have also coded in Java and soon I switched over to Python. The reason I liked and chose Python was because of its flexibility and simplicity.

I am also familiar with the web development stuff: HTML, CSS, MySQL, PHP, JavaScript and more. I was also given a project to develop a restaurant web application while I was intern at ColoreCow during my summer break previous year.

I qualified Google Code Jam qualifiers and also participated in IEEE Xtreme 10.0(secured AIR 22). I have a deep interest in programming and contributing to open source world.

Contributions to Sympy

Well I started contributing to Sympy about 3 months back and in this short period of time I have learned a lot of things about Sympy and I have known how powerful this Computer Algebra System is. I started of introducing myself to the Gitter channel and I made my doubts cleared about how do I make my first contribution. All the members are active, I used to get the response pretty soon. Gradually I got myself comfortable with Sympy's devlopment workflow. Even now at any point I have a doubt, I throw it in Gitter or in IRC channel and make it clear by discussions.

The most interesting feature of Sympy that I found was the solvers module. It is a module that is capable of solving all types of equations, making it one of the powerful features. To make it more powerful and efficient I decided to work on this particular module. I mainly focused on its newest module solveset.

>>> check_assumptions(-5, integer=False, positive=True)
False                  # At present

>>> check_assumptions(-5, True, integer=False, positive=True)
(False, ('integer', 'positive'))           # After this PR.

  • (unmerged) PR #12224 it was in reference to issue #12217 that pointed out a bug in solveset.

  • (merged) PR #12311 this PR just fixes a typo error in bivariate.py module.

  • (unmerged) PR #12245 it was a reference to issue #12239 that required solveset to support symbolic functions.

# real domain
>>> solveset(f(1)**2 - 1, f(1), S.Reals)
{-1, 1}

#complex domain

>>> solveset(f(1)**2 + 1, f(1))
{-I, I}

  • (unmerged) PR #12395 this PR was created to implement the logic of log solver i.e. implementing logarithmic equations solver as part of the transolve. I tried to implement the helper function for it _logsolver.

  • (unmerged) PR #12394 this PR added few examples to the docs to increase the understanding of the functionality of FiniteSet, so that one finds it easy to implement.

Issues/bugs reported

  • Issue #12146: this issue was created to add more functionality to check_assumption function. (PR #12147](https://github.com/sympy/sympy/pull/12147) was created in its reference.

  • Issue #12217 this was created to report a issue that solveset does'nt solve for a constant number like solve does. The discussion resulted that solveset should be made to solve only for symbols. Also it resulted in a bug that solveset should raise ValueError when a constant is specified as symbol rather than an EmptySet which resulted in PR #12224.

I have tried to implement but few test cases are not handled. I am trying to make it possible to handle all test cases.

>>> solveset(sqrt(2) - 1, 1)
EmptySet()      # At present

>>> solveset(sqrt(2) - 1, 1)
# raise ValueError  (After implementation)

  • Issue #12243 this is a discussion for the issue of solveset to implement transcendental equation solver. Previous year kshitij10496 created PR #11540 that raised similar points.

  • Issue#12340 a discussion rather than an issue that would help me understand what work has been done so far to implement trigonometric equation solver and would also help me in implementing it.

  • Even raised a question in stackoverflow, that resulted in the documentation of Singleton. Here's the PR

The Project

Brief Overview

Solving any type of equations is one of the most essential and powerful feature of any Computer Algebra System. For Sympy it is Solvers. Previously solver used solve for solving any type of equations. No doubt solve does the work pretty amazingly but it has few issues. Few of the major issues are:

  1. It doesn't have a consistent output for various types of solutions It needs to return a lot of types of solutions consistently:

    • single solution : x == 1
    • Multiple solutions: x**2 == 1
    • No Solution: x**2 + 1 == 0; x is real
    • Interval of solution: floor(x) == 0
    • Infinitely many solutions: sin(x) == 0
    • Multivariate functions with point solutions x2 + y2 == 0
    • Multivariate functions with non point solution x2 + y2 == 1
    • System of equations x + y == 1 and x - y == 0
    • Relational x > 0 And the most important case "We don't Know"

  2. The input API is also a mess, there are a lot of parameter. Many of them are not needed and they makes it hard for the user and the developers to work on solvers.

  3. There are cases like finding the maxima and minima of function using critical points where it is important to know if it has returned all the solutions. solve does not guarantee this.

Consequently this solveset module was created to fix all such issues and make it more powerful than solve. For the past 3 years solveset is under development of becoming at least as powerful as solve. In GSoC 2016 @Shekharrajak and @kshitij10496 did a lot of enhancement in solveset module, but still many of the things are left and I want to start from where they have left. My main area of concern would be:

  • Transcendental Equation solver: solve uses _tsolve and bivariate.py to handle transcendental equation. _tsolve does a very good job in solving a large space of transcendental equations. The problem lies in the fact that it's codebase is very messy and not extensible. Also, adding a Set output interface to _tsolve is quite complicated. Hence, it's very important to write a more modular and extensible transcendental equation solver. We encourage you to leverage the power of bivariate module to implement the new transolve.

  • Integrating helper solvers with solveset: Currently, solveset only solves a single equation for a single variable. In the future, we expect it to be capable of solving a system of equations and for more than one variable. linsolve: Solves a system of linear equations nonlinsolve: Solves a system of non-linear equations solve_decomposition: Solves a varied class of equations using the concept of Rewriting and Decomposition These are the helper functions that have been implemented in solveset during the past few years. We would like to have all these solvers(including transolve) to be integrating in solveset so as to increase its power.

  • Build the set infrastructure: This includes implementing functions to handle multidimensional ImageSet etc., This part must go hand in hand with the improvements in the solvers as set module can be a universe in itself. Also there can be fundamental limits on the things you can do.

  • nonlinsolve is not able to handle system having trigonometric/transcendental equations correctly all the time. Improve solveset's trigonometric solver and handle trig system of equations separately in nonlinsolve.

  • Also solveset is not able to handle symbolic function issue# 12239, I have tried to implement it in my PR #12245. I hope to implement it in much nicer way so as to maintain the flexibility of solveset.

The Plan

Basically my intentions would be to make solveset at least as powerful as solve and closing #10006.

I will also focus on implementing #11540 and #9774.

1) Transcendental Equation Solver(implementing transolve)

Transcendental Function: It is an analytic function that does not satisfy a polynomial equation in contrast to an algebraic function.

examples:

  • exponential function

  • Logarithm

  • Trignometric Functions

Transcendental Equations: It is an equation containing a transcendental function of the variable being solved for.

examples:

  • x = cos(x)

solveset is not able to handle transcendental equations. At present it returns a ConditionSet for such equations type. Work needs to be done on the following:

  • Logarthmic equation solver
  • Exponential equation solver
  • Equations solvable by LambertW
  • Bivariate Solver

We need to implement transolve for solveset, and during my GSoC period I will be implementing it.

1.1) Equations solvable by LambertW function

solve module is able to handle such type of transcendental equation quite comfortably, it is handled by its powerful sub module bivariate.py.

>>> solve(x + exp(x), x)
[-LambertW(1)]

>>> solveset(x + exp(x), x)
ConditionSet(x, Eq(x + exp(x), 0), Complexes((-oo, oo) x (-oo, oo), False))

Brief overview of LambertW function:

The Lambert W-function, also called the omega function, is the inverse function of

Solving,

, where

, where W is the Lambert function.

In general and simpler terms, any equation that can be written in the form

A + Bx + Clog(D + Ex) = 0 has solution in Lambert function.

The solution(s) write:

where,

1.2) Exponential Equation Solvers

At present solveset is not able to handle exponential equations.Some type of equations are partially handled.

Def: In simpler words

Exponential equations are the ones in which variables occur in the exponent.

>>> solveset(2**x - 32, x, S.Reals)
{log(32)/log(2)}        # not simplified, partially solved

>>> solveset(2**x - 32, x, S.Reals)
{5}                     # correct output

>>> solveset(2**x - 32**(x+1), x, S.Reals)
ConditionSet(x, Eq(2**x - 32**(x + 1), 0), (-oo, oo))          # returns ConditionSet

>>> solveset(2**x - 32**(x+1), x, S.Reals)
{-5/4}                    # should return after implementation

Reason for partial handling is that solveset solve exponents just by converting to logs and calling the _invert there is no simplification thereafter.

Like these there are other variants of exponential equations which solveset does not handles.

1.3) Trignometric Equation Solver

Trignometric Equations are the equations involving trignometric functions of a variable.

These equations have two varieties of solutions, namely

Principle Solutions solutions for which 0 <= x < 2⋅π

General Solutions solutions involving integer n.

solveset uses _solve_trig to solve such type of equations and focuses on returning general solutions. But still _solve_trig is unable to solve a variety of problems. Following are the issues that it faces and I would like to fix this during my GSoC term.

  • Simplification for some type of problems has to be done, like:
>>> solveset(sin(2*x) + sin(4*x) + sin(6*x) , x, S.Reals)
{2⋅n⋅π | n ∊ ℤ} ∪ {2⋅n⋅π + π | n ∊ ℤ} ∪ ⎨2⋅n⋅π + ─ | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π - ─ | n ∊
                                        ⎩        2        ⎭   ⎩        2      

  ⎫   ⎧        3⋅π        ⎫   ⎧        3⋅π        ⎫   ⎧        π        ⎫   ⎧ 
 ℤ⎬ ∪ ⎨2⋅n⋅π - ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π - ─ | n ∊ ℤ⎬ ∪ ⎨2
  ⎭   ⎩         4         ⎭   ⎩         4         ⎭   ⎩        4        ⎭   ⎩ 

       π        ⎫   ⎧        5⋅π        ⎫   ⎧        5⋅π        ⎫   ⎧        π
⋅n⋅π + ─ | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π - ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π - ─
       4        ⎭   ⎩         6         ⎭   ⎩         6         ⎭   ⎩        6

        ⎫   ⎧        π        ⎫
 | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─ | n ∊ ℤ⎬
        ⎭   ⎩        6        ⎭


This could be simplified to

(n⋅π / 4) ,  (n⋅π ± π/6)

  • Improving the result of solveset(sin(x), x) from {2⋅n⋅π | n ∊ ℤ} ∪ {2⋅n⋅π + π | n ∊ ℤ} to just {n⋅π | n ∊ ℤ}

  • inability to solve nested trignometric expressions issue#10217

>>> eq=cos((sin(x)+1)) - 1
>>> solveset(eq,domain=S.Reals)
ConditionSet(x, Eq(cos(sin(x) + 1) - 1, 0), (-oo, oo))
  • problems like:
>>>  solveset(sin(x)**2 + 1 - 2*sin(x),x )  # raises NotImplementedError

Possible fix: such problems are the ones that can be converted to polynomial equations(by the principle of Decomposition and Rewriting) and thus solved. For these type of problems we can have an internal call to solve_decomposition which solves the problem.

Previous year @Shekharrajak tried to improve _solve_trig, PR##10733, PR##10898, PR#10713 but I guess these problems still prevails.

I summarised all the problems and created an issue for the discussion purpose so as to get the best way to fix them issue##12340.

1.4) Logarithmic solver

solveset is unable to handle complex logarithmic problems . This needs to be implemented as part of transolve .

Previously kshitij10496 tried to implement the log solver in his PR#11540 but still it need a lot of work to be done.

>>> solveset(log(x-3) + log(x-2) - log(2*x + 24),x)
ConditionSet(x, Eq(log(x - 3) + log(x - 2) - log(2*(x + 12)), 0), Complexes((-oo, oo) x (-oo, oo), False))

I too tried to implement _logsolver (a helper function for transolve) in my PR #12395. This will increase the capability of solveset to solve logarithmic equations efficiently and precisely. I am working on it to make it merge.

2) Handling symbolic functions

solveset is not able to handle symbolic functions, i.e. if functions are specified as variables, whereas solve does.

issue#12239

solveset(f(1)**2 - 1, f(1))
 # raises NotImplementeError

whereas `solve` does,

solve(f(1)**2 - 1, f(1))
[-1, 1]

solveset was not able to handle such type probably due to the fact that functions do not show up as free symbols therefore a NotImplementedError was raised.

I tried to implement this is my PR#12245

Implementation logic I tried to solve by replacing the function term f(1) by a dummy variable and then calling _solveset to solve as normal equations, and thus the problem could be solved.

I would like to enhance this logic a bit more so that the flexibility of the solveset is retained.

Execution

Whatever issues are there, they are not solved unless properly executed and planned. Therefore to get a better result out of what I have proposed I divide my work into three phases.

Phase I

1) Implementing transolve During the first phase I will try to implement transolve which will be one of the major task during the whole period.

  • In depth study on how _tsolve is so powerful and then implementing transolve which will be as powerful as _tsolve but with folllowing enhancement, i.e

    • the code will not be messy, rather the whole transolve will be smartly and efficiently coded.

    • much more modular and extensible.

Following is the pseudo code representation of transolve:

2) Implementing LambertW Functions equations solvable by lambertW are an important part of transolve.

At present solveset is unable to handle such type of equations but implementation of transolve will result in its implementation.

solve greatly depends on bivariate.py module to solve such equations. transolve can also leverage the power of this module to implement lambertW functions.

Implementation

Basically there are three variants for equation A + Bx + Clog(D + Ex) = 0, namely

a.1) b**b = r, for r not {0, 1}

a.2) b*(E*log(b) + D)**C = r

a.3) C*log(E*b + D) + D*b = r

They are already in the general form of logs.

b.1) (E*b + D)*exp(B*b + G) = R

b.2) -E*b + G*exp(B*b + H) = D

These form have exponents that must be converted to logs.

c) B*P**(C*b + G) - E*b = D

`pow` type form, also needs to be converted to logs

We only need to simplify the problem into these forms and get the required values accordingly and the solution can thus be formed.

taking,

    log(x) + 2**x = 0

    this problem is of the form `a.3)` .

    it is in the standard form therefore

    A = 0, B = 2, C = 1, D = 0, E = 1

    substituting these values we get

    x = 0 + 1/2(W(t))

    t = 2*exp(0)  =>  t = 2

    therefore, x = 1/2(W(2))

Similarly many different variants can be solved.

3) Implementing Exponential solver

Another part while implementing transolve will be incorporating exponential equation solver.

At present some type of such equations are handled. Most of them are either partially handled or are not implemented(returns ConditionSet) as mentioned above.

Though already solve has implemented exponential equation solver and handling is done pretty well, such equations are handled by _tsolve and even solve_lambert of bivariate.py, and we can implement it in similar fashion in solvesetas well but I thought of implementing it in a much basic way, so that dependency on bivarite.py gets reduced and transolve handles it independently. I will try to make my method more efficient and robust.

I would like the basic math approach to solve such equations as I have mentioned above.

Implementation

General approach to solve any exponential equation is:

Step 1: Determine whether the equation can be written using the same base.

Step 2: If so, rewrite the problem using the same base.

Step 3: Use properties of exponents to simplify the problem.

Step 4: Once the bases are the same, drop the bases and set the exponents equal to each other.

Step 5: Finish solving the problem by isolating the variable.

if the equation cannot be written using same base proceed as:

Step 1: Take the common logarithm or natural logarithm of each side.

Step 2: Use the properties of logarithms to rewrite the problem. Specifically,

Step 3: Finish solving the problem by isolating the variable.

A bit of the following code that justifies my approach(though a lot have to be done in the code). This is just an ad hoc implementation that solves only cases having same bases, but could be the basis of future implementation. Will try to generalize it during the period.

from sympy import *
from sympy.abc import x, y
from sympy.solvers.solveset import _solveset
from sympy import perfect_power

def _chk_base(n, m):
    grt_num = max(n,m)
    sml_num = min(n,m)
    try:
        if perfect_power(grt_num)[0] == sml_num:
            return perfect_power(grt_num)[1], 0
        else:
            p_sml_num = perfect_power(sml_num)
            g_grt_num = perfect_power(grt_num)
            if p_sml_num[0] == g_grt_num[0]:
                return p_sml_num[1], g_grt_num[1]
            else:
                return False, False
    except:
        return False, False
    
def chk_base(f, symbol, domain = S.Reals):
    f_arg = f.args
    if len(f_arg) == 2:
        first_arg = f_arg[0]
        second_arg = f_arg[1]
        if second_arg.free_symbols:
            base, expo = second_arg.args
            pow_value = second_arg
        elif first_arg.free_symbol:
            base, expo = first_arg.args
            pow_value = first_arg

        number_1 = base
        number_2 = -(f - pow_value)
        rhs, rhs_2 = _chk_base(number_1, number_2)
        if rhs is False:
            raise NotImplementedError('Not implemented if bases are not same')
        else:
            if not rhs_2:
                try:
                    if perfect_power(number_1)[1] == rhs:
                        expo = expo*rhs
                        try:
                            rhs = perfect_power(number_2)[1]
                        except:
                            rhs = 1
                except:
                    rhs = rhs
                result = _solveset(expo - rhs, symbol, domain)
            else:
                if perfect_power(number_1)[1] == rhs:
                    expo = expo*rhs
                    result = _solveset(expo - rhs_2, symbol, domain)
                else:
                    expo = expo*rhs_2
                    result = _solveset(expo - rhs, symbol, domain)
    return result
       
def expo_eq(f, symbol, domain=S.Reals):
    f = sympify(f)
    return chk_base(f, symbol,domain)

Phase 2

Phase 2 will start after transolve has been implemented

1) First thing will be to complete all the leftovers of Phase 1 so as to carry out smooth implementation of the things of Phase 2

2) Improving _solve_trig function As mentioned above about the how flexible present _solve_trig is and what are the things that are to be done issues will be solved accordingly.

I have discussion in the issue#12340 regarding _solve_trig, and I got the following deductions:

  • Equations that can be converted to polynomial equations can be solved using the principle of Rewriting and Decomposition(solve_decomposition). @Kshitij10496 suggested that solve_decomposition should be used only when transolve is implemented so as to increase the coverage of equations solved by solve_decompisiton and solveset in turn.
solveset(sin(x)**2 + 1 - 2*sin(x),x )

can be solved as replacing sin(x) = y

therfore eq. reduced to -->  y**2 + 1 - 2*y

Therefore for such specific case of trigonometric equation we can have an internal call to solve_decomposition as the base case when transolve is unable to solve the given equation.

  • Another thing will be to try to fix the problem of simplifying trigonometric equations.

    Discussion revealed that this issue is primarily due to the lack proper algorithm for unifying two ImageSet objects such as 2npi and 2npi + pi. Previous year @Shekharrajak and @Kshitij10496 tried to implement some heuristics(such as genform). During my work period I will try to figure out the necessary things that could solve this issue.

Recently @Shekharrajak implemented ImageSet Union in his PR #12011 so as to make solve_trig more efficient. I am trying to work with him to make the PR merge so that implementation of the above mentioned issue can be resolved.

3) Improvement in handling transcendental and trigonometric system of equations After successfully implementing transolve and improving _solve_trig, I can try to implement the newly created nonlinsolve to make it capable of handling transcendental and trigonometric system of equations.

At present due to lack of capability of solveset handling such equations nonlinsolve is unable to solve such system of equations. But once transolve is perfectly implemented work on this particular functionality can be done. I will try to implement it during my GSoC period.

Phase 3

  • This phase would be the one in which I will try to finish off my tasks that are pending and also the tasks remaining during Phase 1 and Phase 2. Like, implementing symbolic functions. I will also try to explore solveset(things that solveset can't do right now and also the things it is capable of doing) to make it more robust and finally closing the issue #10006.

  • Also try to solve issues and minor bugs that were raise during Phase 1 and Phase 2 implementation.

This would probably be the revision and exploration phase, that would require all the things done as per the requirements.

Timeline

This project will definitely extend the functionality of solveset and might take more time, but I am confident and I assure that I will devote all my time in this project and try to finish what I proposed. I will be having my semester exams till end of May(tentative), but even during this time I will try to give 2-3 hours daily and thereafter I will devote all of my time(about 40-50 hrs a week or even more). College will be started in August and not enough work happens during the first month so I can work with full devotion.

Community Bonding Period(May 5 - 30, 2017)(exam time)

  • In this period I will have a deep understanding of the solvers and other related module and also plan how to implement what I have proposed.

  • Also I will have discussions and meetings with the mentors and we will come up with the efficient way.

Week 1,2,3(May 30 - June 19)

  • Implementing transolve on the basis of the discussions.

  • Incorporating LambertW function using the powerful bivariate.py .

  • Also incorporating exponential equation solver and log solver as part of the transolve.

Week 4,5(June 20 - July 3)

  • Writing test cases.

  • Implementing what has been left during first three weeks.

  • Fixing bugs and issues that may have raised during previous implementation.

Week 6(July 4 - July 10)

  • Improvement in _solve_trig starts.

  • Analyzing how solve solves and discussing with mentors and arriving at a plan.

Week 7,8(July 11 - July 24)

  • Work on ImageSet Union, make it efficient and try to merge it.

  • Implementing a specific case of trigonometric equations as a base case using solve_decomposition.

  • Adding test cases and minor bug fixes.

Week 9,10,11(July 25 - Aug 14)

  • Implementing trigonometric equation solver.

  • Simplified general form solution of trigonometric equations.

  • Implementing set algorithms and building set infrastructure to arrive at above point.

  • Writing tests and fixing minor bugs/issues.

Week 12,13(Aug 15 - Aug 29)

  • Finishing above work if it is remaining.

  • Implementing other functionalities that were previously raised like implementing symbolic function.

  • Replace all internal calls from solve to solveset.

  • Analyzing what all things that can be to improve transolve to make it more better.

Any Commitments/Plans(during GSoC)

  • I don't have any specific commitments for the summer, therefore I can devote my whole time.

  • I will be writing blogs of what all discussions have taken place and also what and how I have implemented.

  • I will only have my exams during the Community Bonding Period, therefore I will spend a bit less of my time but as soon as they get over I will give all of my time(will also try to compensate the time lost due to exams).

Post GSoC

  • If there are things that are left unimplemented I will try to complete post GSoC and even I will also continue my contributions to sympy and help the new contributors.

  • As I mentioned I started coding with C++, I will also try to contribute to SymEngine.

  • Being a Computer Science undergraduate I would love if Sympy supported Graph Theory , there are many Computer Algebra Systems that support GT. If got chance I would like to implement it( will definitely try).

References