GSoC 2016 Solvers Progress - sympy/sympy GitHub Wiki

GSoC 2016 Solvers

  • Students: [Kshitij Saraogi], [Shekhar Prasad Rajak]
  • Mentors: [Amit Kumar], [Harsh Gupta]

Shekhar's Progress

Week # Goals Blog Post Status/PR Links (if any)
Community Bonding nlinsolve nlinsolve and non symbol solver PR #11111PR #11128
1 nlinsolve continue nlinsolve features -
2 Simplified Solution for Trigonometric equation Week 2 blog #11188
3 nonlinsolve and simplified trig soln week 3 factor_list PR
4 Connecting Diophantine and solveset to get Integer solution Week 4 #11234 #11239
5 Trig inequality Week 4, week 5 #11257,#11280
6 Worked on previous PR week 6 11334
7 Trigonometric, Ineq and previous PR Week 7 #11339, #11343
8 Improving prev PRs and Trig solver week 8 #11371
9 Improving trig and inverse trig basic methods, working on #2720 Week 9 #11409, #11424
10 Worked on previous PRs Week 10 --
11 Improved previous PR and worked in eliminate() Week 11 #11485
12 Worked in previous PR Week 12 --
13 documentation and tried for merge Week 13 #11532

Kshitij's Progress

Week # Goals Blog Post Status/PR Links (if any)
Community Bonding Audit tsolve method in the old solvers Auditing tsolve --
1 Work on intersections of ImageSet The One with Intersection PR#11149, PR#11164
2 Method for computing a function's range The One with Function Range (Part I) PR#11141
3 Implementing methods for finding the range of a function The One with Function Range (Part II) PR#11224
4, 5 Developing the functionality to compute period of function The One with Periodicity PR#11277
7 Implementing method for finding the general period of functions The One With Generalised Periodicity PR#11277
8 -- -- --
9 Solving inequalities The One with Inequalities
10, 11 Implementing solvify The One with solvify PR#11458
12 -- -- --
13 -- -- --

Meeting Schedule

Meeting #01

  • Date: 2nd May, 2016
  • Time: 6:30 PM - 7:15 PM (IST)
  • Attendees: Amit Kumar, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Plans for the Community Bonding Period
    Shekhar will remain busy during this period as his college examinations start from Thursday, the 5th of May. His examinations are expected to end by the 14th of May, and he will be up and running then. Meanwhile, Kshitij has no upcoming exams and will be contributing full time from Sunday 8th May 2016.

  • Splitting the project
    We both had proposed to work on a few similar topics in our proposals.
    As there is a lot of task that's needed to be done, Amit suggested us to split the project among ourselves.
    Currently, our two main priorities are implementing the following:

    • Univariate Transcendental equation solver
    • Solving multivariate equations

    Due to his impending exams, Shekhar suggested that he would like to work on the system of nonlinear multivariate equations.
    On the other hand, Kshitij will look into the old transcendental equations solver - tsolve. The motive is to devise ways to develop a modularized and extensible method for handling such equations.

  • Gitter Channel
    Amit stressed on the point to make every discussion open to the community for their reviews and guidance. To that end, Kshitij suggested creating a dedicated Gitter channel. After some deliberation, it was decided to create a public Gitter channel specifically for discussion on the Solvers project. Amit took the responsibility for doing the same.

  • Goals for Shekhar:

    • Look into implementing a system of multivariate equation solver using solve_poly_system.
    • Deadline: Monday 23rd May 2016

  • Goals for Kshitij:

    • Set up a blog as soon as possible.
    • Audit tsolve in the old solver.
    • Read the paper on LambertW function for developing a deeper understanding.
    • Deadline : Friday 13th May 2016

Pull Requests to review (all):

  • PR #10751@kshitij10496: To be reviewed by @aktech
  • PR #10733@Shekharrajak: To be reviwed by @kshitij10496

Meeting #02

  • Date: Sunday 15 May, 2016
  • Time: 10:00 - 11:00AM (IST)
  • Attendees: Harsh Gupta, Amit Kumar, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

Shekhar is starting working on Non Linear System of Equations using solve_poly_system(works pretty well).If there is some symbols that can't be solved using solve_poly_system solve them using known results(substitution method Link1, link3 ) or use this method Link3 (Page 9 : 2.2 example) .

Kshitij is working on _tsolve. He is posting blog about his idea and implementation part by tonight.

Meeting #03

  • Date: 22nd May 2016
  • Time: 11:00 AM - 12:15 PM (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

The meeting started with Kshitij presenting his work in the PR#11141 : the solve_decomposition method.

Here are the issues discussed in the meeting:

  1. Handling an EmptySet returned by solveset
    This is a design issue with two possible approaches:
  • Returning a ConditionSet object stating that this method cannot solve the equation.
  • Returning an EmptySet object - specifying that no solutions exist for such an equation.
    Test cases: 1/ln(x) and 1/tan(x).
    Harsh suggested that including the infinities(both S.Infinity and S.NegativeInfinity) in the real domain would be useful for this case and for the overall development of solveset.

  1. Finding the range of a function
    Sometimes, the range of a function can be used to decide whether an equation is solvable or not.
    There is no explicit functionality for determining the range in SymPy.
    For instance, solving for x in cos(x) = 2 should have no solution.
    As a result, an EmptySet object is expected. However, current implementation cannot achieve this. A possible technique to calculate the range consist of:

  2. Determining the inverse image of the function (if possible)

  3. Find the domain of the inverted function. For this, Amit suggested the use of the not_empty_in function.

  4. Intersection of an ImageSet with an Interval
    Following the determination of the range of the function (an Interval object), we will need to determine what values satisfy the equation. The ability to compute the intersection of an ImageSet with an Interval will be needed.
    Harsh shared an idea of solving this issue as follows:

    1. Extract the Lambda function of the ImageSet.
    2. Invert the expression of this Lambda function for the boundary values of Interval object.
    3. These values are used to define a new Interval object.
    4. Take the intersection of the base_set of the ImageSet with the new Interval object.
    5. Substitute these values back into the original Lambda function to obtain the intersection set.

This was followed by a discussion on the implementation of nlinsolve and a method for solving equations for non-symbols. PR#11111.

Shekhar's part of the discussion :

  1. About the PR#11128 : The PR was not really necessary for solveset right now.

2.PR#11111 nlinsolve method was partially created. Remaining part is substitution method(when equations poly and non polynomial) and positive dimensional system.

Shekhar is trying to get solution from groebner basis for positive dimensional system.

In substitution method, solveset is used in some steps to solve for individual symbols. So solveset may return Intersection/Imageset

example :

    In [ ]: solveset(z + exp(2*x) - sin(y),x,S.Reals)
    Out[ ]: (-∞, ∞) ∩ {log(-(z - sin(y)))}

so if we want to check unsolved symbols in the solution then need to check imageset/intersection.

  • Goals for Kshitij:

    • Write a blog post on solve_decomposition
    • Read about the Extended Reals and document the pros and cons of its implementation.
    • Develop a method for finding the range of a function.
    • Implement the intersection technique of an ImageSet with an Interval

  • Goals for Shekhar:

    • Edit blog with proper implementation and problems he is facing.
    • Work on positive dimensional system solver, substitution method.

At the end, Wednesday, 25th May was decided to be the date of the next meeting. Time to code !

Meeting #04

  • Date: 26 May, 2016
  • Time: 7:30 PM - 8:45 PM (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion :

    • PR #11149 : A very brief review of the PR and its importance in handling intersection operation of certain sets (Integers, Naturals) with Intervals.
    • PR #11164 : Extended discussion on the various cases of the technique implemented in this PR. A particular, interesting case is that of handling complex values returned after inverting the Lambda expression. As only real-valued intervals exist, the way of handling the complex values was discussed.
    • Range: The not_empty_in method cannot be used for our purpose here. We will have to implement a new method here. For this, Harsh and Amit suggested researching the mailing list and previous discussions for ideas.

  • Goals for Kshitij:

    • Implement the feature of handling complex values in PR#11164
    • Read about the possible ways to implement the range of a function

  • Shekhar's part of the discussion :

    • nlinsolve PR#11111 currently it returns solution in same order as the symbols are given for zero dimensional system. But in positive dimensional system and substitution method returns solution is not in same order and also replace Dict with tuple in final solution.
  • Trigonometric Inequality solver is not giving solution in general form. ex:
In [4]: solveset(2*sin(x)-1<0, x, S.Reals)
Out[4]: 
⎛    π⎞   ⎛5⋅π   ⎞
⎜-∞, ─⎟ ∪ ⎜───, ∞⎟
⎝    6⎠   ⎝ 6    ⎠

We can generalize this to (2*π*n - 7*π/6) < x < (2*π*n + π/6).

  • Goals for Shekhar:

    • Make nlinsolve free from Dict and update the blog.
    • Search more about trigonometric inequalities.

Meeting #05

  • Date: 29 May, 2016
  • Time: 5:00 PM - 6:30 PM (IST)
  • Attendees: Amit Kumar, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion : For finding the range of a function, Amit suggested looking into the PRs#2723 and PR#2925. Also, PR#11164 is up for review and Amit will try to review it before the next meeting.

  • Goals for Kshitij:

  • Try to implement a method for finding the range of a function in a given domain.

  • Shekhar's part of the discussion :

    • Shekhar was trying to get extended solution for Trigonometric inequality. For that we need to find domain of the expression. We have to check mainly sqrt and denominators. Expressions inside sqrt should be greater than zero and denominator expression = 0 solution should be excluded from the overall domain. We can use decompogen to get domain.

    • nlinsolve XFAIL case test_issue_2777 was failing because there is need of checking whether solution is making denom = 0. If yes then remove that solution. Need little improvement for these cases.

    • There is comparison error for one test case. Amit will try to check that comparison error.

  • Goals for Shekhar:

Meeting #06

  • Date: 5 June, 2016
  • Time: 6:00 - 7:00 PM (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion :

    • Discussion on the design of the methods(function_range and continuous_in) for finding the range of a function.
    • Instead of using the singularities function, we are using the general way of finding the singularities.
    • Also, we will deal with domain constraints in case of sqrt and log functions.

  • Goals for Kshitij:

  • Shekhar's part of the discussion :

    • PR #11188 simplified general solution: Found some cases like 2*sin(x) - 2*sqrt(3)*cos(x) - sqrt(3)*tan(x) +3 that is easy to solve when we do factor the eq correctly.But solveset is hanging for these types of equations. We first do factor of original eq (Trig eq.) then rewrite in into exp form for further steps.

  • Goals for Shekhar:

    • PR #11188 improve the code for more testcases.

Meeting #07

  • Date: 10 June, 2016
  • Time: - (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion :

    • Completed the implementation of the methods for finding the domain of a function
    • Few functions such as 1/tan(x) and 1/log(x) yield incorrect answers in the Reals domain. For this Harsh suggested the use of Extended Reals as the domain.
    • These functions need to be shifted to the util module from the singularities.

  • Goals for Kshitij:

    • Study extended reals and their applicability.
    • Complete PR#11224.

  • Shekhar's part of the discussion :

    • PR #11188 simplified general solution: reduce_imageset function is for reducing number of Imageset. So shift it to Union (Imageset union) it is related to Set. Some testcases is failing because of Dummy n. Use one dummy.

    • PR #11111 nonlinsolve : some testcase is failing because of negative comes inside log check it.

  • Goals for Shekhar:

    • shift code for simplification of imageset into Union defined in sets/sets.py.

    • Edit testcases of nonlinsolve.

    • Integers solution using diophantine.

Meeting #08

  • Date: 19 June, 2016
  • Time: 6:30 - 7:45 (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion :

    • solveset(1/tan(x), x, Interval(0, 2*pi)) returns EmptySet.
      Expected answer: {pi/2, 3*pi/2} This is due to the check_domain function which checks the continuity of tan(x) at pi/2 and 3*pi/2 Resolution : Try to replace check_domain with newly implemented continuous_domain.

    • Automatic Simplification of expressions such as x/x to 1. This leads to incorrect result for domains. For example, domain of x/x is S.Reals - {0}. However, due to automatic simplification, we get S.Reals as the result.

  • Goals for Kshitij:

    • Update PR#11224 with the review suggestions.
    • Make a post on the mailing list regarding automatic simplification.

  • Shekhar's part of the discussion :

    • PR #11111 nonlinsolve : Need more clear documentation for substitution function and comments as well.

    • PR #11188 simplified general solution: I shifted the code to _union (ImageSet union) and created new helper function _union_simplify.

    • PR #11234 solveset_integers to get solution in S.Integers Domain.

    • PR #11257 There is problems in old solver already issues are opened for simple Trig inequalities one of them is #9721. Created a function solveset_univariate_trig_inequality to handle Trig ineq. Work in progress.

  • Goals for Shekhar:

    • PR #11111 nonlinsolve - add more testcases and import all cases from old solve. Improve docstring.
    • PR #11257 work continue improve the code.

Meeting #09

  • Date: 26 June, 2016
  • Time: 10:00 PM - 11:15 PM (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion :

    • In order to mitigate the effects of automatic simplification on solveset and the domain of After much discussion on singularities and domain, it was decided that removable singularities should be returned as part of the domain( in the result returned by continuous_domain).

  • Goals for Kshitij:

  • Update PR#11277 for final review.
  • Look for ways to incorporate removable singularities in the domain.
  • Shekhar's part of the discussion :

  • PR #11111 nonlinsolve : Remove dependency (It was using old solvers_invert method, because it can accept list of symbols).

  • PR #11188 simplified general solution: This PR passes all the check but sometimes it fails if we run the bin/test locally. All the testcases works fine, there might be the problem of Dummy variables. Still finding the solution.

  • PR #11234 solveset_integers : to get solution in S.Integers Domain. We discussed on this comment. Main point was solveset should return complete solution but we don't know exactly whether diophantine is returning all the soln or not. If there is some eq. type for which diophantine is not implemented or returns missing soln then solveset_integers should return ConditionSet for these cases.

  • Also discussed to improve communication skill and write proper comments.

  • Goals for Shekhar:

    • Read docs and blogs for diophantine module and check for which diophantine eq type soln is incomplete.

    • Complete #11111 (nonlinsolve) , PR #11188 (simplified general solution).

Meeting #10

  • Date: 2 July, 2016
  • Time: 10:00 PM - 11:15 PM (IST)
  • Attendees: Amit Kumar, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion :

    -todo

  • Goals for Kshitij: -todo

  • Shekhar's part of the discussion :

  • PR #11111 nonlinsolve : discussed about breaking code into functions to make it more modular and returning conditionset when nonlinsolve not able to solve system.

  • PR #11188 simplified general solution: The issue(sometimes pass the testcases, sometimes fails) is fixed now. I think by using FiniteSet it will arrange args in same order always that fixes the issue.

  • PR #11334 solveset_integers : to get solution in S.Integers Domain. I observed this in diophantine.So it seems we need to permute sign only when eq type is general_sum_of_even_powers, homogeneous_ternary_quadratic, pythagorean and updated the PR.

  • Goals for Shekhar:

    • read diophantine module and get soln for this comment.

    • Complete #11111 (nonlinsolve) , PR #11188 (simplified general solution).

Meeting #11

  • Date: 06 July, 2016
  • Time: 8:00 PM - 9 PM (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion :

    -todo

  • Goals for Kshitij: -todo

  • Shekhar's part of the discussion :

  • PR #11111 nonlinsolve : Discussed about how to improve code quality and D.R.Y (Don't repeat yourself), loose coupling concepts in programming.

  • #11343 : No need of defining new attribute put_values im imageset.

In [3]: img = ImageSet(Lambda((n, m), n**2 + m) , S.Reals)

In [4]: img.put_values({n: 1, m: 2})
Out[4]: {3}

One should first check that if value (to be substituted) is in base_set of not, if yes then using imageset.lamda(values_for_lambda_var) user can get the value. Edit the PR and in the docstring write about how to substitute a value in lambda variables.

Meeting #12

  • Date: 25 July, 2016
  • Time: 11:00 PM - 12 PM (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

  • Kshitij's part of the discussion :

    -todo

  • Goals for Kshitij: -todo

  • Shekhar's part of the discussion :

  • Goals for Shekhar:

Meeting #13

  • Date: 07 August, 2016
  • Time: 11:00 PM - 11:30 PM (IST)
  • Attendees: Amit Kumar, Harsh Gupta, Kshitij Saraogi, Shekhar Prasad Rajak
Minutes of Meeting:

With the endterm evaluation deadline fast approaching, the motive of the meeting was to discuss our goals for the next couple of weeks. This will help us have a clearly identify the tasks we need to complete so as to achieve a passing grade.

  • Endterm evaluation goals

    • For Kshitij

    1. Discussion on PR#11458. Getting this merged during the SoC should be a top priority.

    2. Work on transolve: transcendental equation solver It is expected of me to complete the transolve and open a WIP (atleast) during the next 2 weeks. However, it might not get merged during the official SoC period. If so, it will be my responsibility to see it through even after the SoC is over.

For Shekhar :

Goal for next week :

  • Complete nonlinsolve #11111 , Simplified solution for trigonometric equations #11188, Solveset Integers for integer solution :#11234

  • Check coverage_report and improve it.

Works I mentioned in project :

  • Improved Trigonometric Equation Solver , Simplified general form for trigonometric solution
  • Nonlinear Multivariate System of Equations
  • Transcendental (Kshitij is working on it)
  • Integer solution of a linear equation
  • Inequalities and Equation solver having functions (Kshitij is working on it)

Work Completed :

Work in Progress :

TODO :

also need to add inverse trig formula/identities in simplify

  • define helper function for _solve_trig which will be called when it find the trig equation of the type sin(x)*cos(y) + sin(y)*cos(x) (we first rewrite of the form sincos then using match we can find equation of the type p*sin(x) + q*cos(x) then this helper function will be called. So it will make it sin(x + y) (dividing sqrt(p**2 + q**2) then get the trig identity form). Using solve_decompogen we can solve sin(x + y) similarly we can use more trig identities.

  • I worked on https://github.com/sympy/sympy/issues/2720 ( define eliminate()), (after the main project this will be discussed).

Few more points :