# GSoC 2016 Solvers Progress

Shekhar Prasad Rajak edited this page Aug 22, 2016 · 50 revisions

# 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.

• Goals for Shekhar:

### 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 :

• nonlinsolve https://github.com/sympy/sympy/pull/11111 : We have discussed about this PR many times. It is almost done, but there is need of improvement in code quality. it became little messy because `substitution` function is handling all kind of solution type(ImageSet, FiniteSet, ConditionSet, Intersection, Complement).

• I have written blog post for each week. Details regarding my works, issues I faced, ideas, todo part (and works that can be done in future) are in the posts. blog link : http://shekharrajak.github.io/

##### Clone this wiki locally
You can’t perform that action at this time.
Press h to open a hovercard with more details.