GSoC 2017 Application Ekansh Purohit: Solvers Transcendental Equation Solver & Extending solveset - sympy/sympy GitHub Wiki
NOTE: This proposal is not yet complete and will be updated continuously till 3rd April
About Me
Username and Contact Information
Name: Ekansh Purohit
Age: 20
University: International Institution of Information Technology, Hyderabad
E-mail: [email protected]
IRC handle: E-DEA
Github Username: E-DEA
Personal background
Hello, I'm Ekansh Purohit, a second year undergraduate student pursuing a degree in (B.Tech + M.S.) in Computer Science at International Institute of Information Technology, Hyderabad, India.
I gained interest in coding and Open Source contribution at the end of my high school and since then then have learned various programming languages which include C, C++, Python and Swift. I have been working in these languages for a year now and have explored them up to a considerable extent and also created many projects based on these like:
-
Meeting Minutes creator(using Web2py)
-
A Tetris Game(using pygame)
-
A custom Brick-Breaker game(using OpenGL3.0)
-
A modified version of game - Bloxorz(called Tumblerz using OpenGL3.0)
-
A mobile application for Fabulyst(on iOS using swift)
Apart from all these, after coming to college I have learned various technologies and frameworks like OpenGL3.0, WebGL, MySQL, Latex etc. to make various kinds of applications or handle data. Also i have learned how to work with various control version systems like Git and Mercurial.
I work on Ubuntu 16.04 LTS with Atom and Sublime Text as my primary text editors. I use this combination of platform and text-editors as they are very user-friendly and powerful with various extensions already available in them and also because of already existing group of developers on various forums where I can get a solution whenever required.
I love working and contributing in python because of it's simple syntax and powerful functions for text and expression processing. It's design philosophy which emphasizes code readability (notably using whitespace indentation to delimit code blocks rather than curly braces or keywords), and a syntax which allows programmers to express concepts in fewer lines of code than possible in languages such as C++ or Java particularly interests me to work in it.
I have been working on sympy for quite some time now and I found these features to be very interesting and are my favorites:
- Ability to make and use various geometrical objects as variables like a line, ellipse, polygon etc. Also use many such geometrical objects to find intersections, areas of common portion etc. with other objects.
>>> from sympy import *
>>> from sympy.geometry import *
>>> x = Point(0, 0)
>>> y = Point(1, 1)
>>> z = Point(2, 2)
>>> zp = Point(1, 0)
>>> Point.is_collinear(x, y, z)
True
>>> t = Triangle(zp, y, x)
>>> t.area
1/2
>>> t.medians[x]
Segment(Point2D(0, 0), Point2D(1, 1/2))
>>> m = t.medians
>>> intersection(m[x], m[y], m[zp])
[Point2D(2/3, 1/3)]
>>> c = Circle(x, 5)
>>> l = Line(Point(5, -5), Point(5, 5))
>>> c.is_tangent(l)
True
>>> l = Line(x, y)
>>> c.is_tangent(l)
False
>>> intersection(c, l)
[Point2D(-5*sqrt(2)/2, -5*sqrt(2)/2), Point2D(5*sqrt(2)/2, 5*sqrt(2)/2)]
- The quantum harmonic oscillator in 3-D in Physics module in which we can find various attributes for a harmonic oscillator like it's energy and radial wave-function.
>> from sympy.physics.sho import E_nl
>>> from sympy import symbols
>>> x, y, z = symbols('x, y, z')
>>> E_nl(x, y, z)
z*(2*x + y + 3/2)
>>> var("r nu l")
(r, nu, l)
>>> R_nl(0, 0, 1, r)
2*2**(3/4)*exp(-r**2)/pi**(1/4)
- The ability of sympy to solve any recurrence relation using
rsolve
in solvers module.
>>> from sympy import Function, rsolve
>>> from sympy.abc import n
>>> y = Function('y')
>>> f = (n - 1)*y(n + 2) - (n**2 + 3*n - 2)*y(n + 1) + 2*n*(n + 1)*y(n)
>>> rsolve(f, y(n))
2**n*C0 + C1*factorial(n)
>>> rsolve(f, y(n), { y(0):0, y(1):3 })
3*2**n - 3*factorial(n)
Project Overview
The Problem & Motivation
sympy already has a very powerful solve
function which takes parameters (function, symbols, flags)
as input and algebraically solves equations and system of equations.
Currently, the supported types include:
- polynomial
- transcendental
- piecewise combinations of the above
- systems of linear and polynomial equations
- systems containing relational expressions.
The output varies according to the input and can be seen by examples:
- boolean or univariate Relational
>>> solve(x < 3)
(-oo < x) & (x < 3)
- single expression and single symbol that is in the expression
>>> solve(x - y, x)
[y]
>>> solve(x - 3, x)
[3]
>>> solve(Eq(x, 3), x)
[3]
- single expression and more than 1 symbol
>>> solve(x - y**2, x, y)
[{x: y**2}]
>>> solve((a + b)*x - b + 2, a, b)
{a: -2, b: 2}
>>> solve((a + b)*x - b**2 + 2, a, b, set=True)
([a, b], {(-sqrt(2), sqrt(2)), (sqrt(2), -sqrt(2))})
>>> solve(x**2 - y**2/exp(x), y, x)
[{y: -x*sqrt(exp(x))}, {y: x*sqrt(exp(x))}]
- to always get a list of solution mappings, use flag dict=True
>>> solve(x - 3, dict=True)
[{x: 3}]
- to get a list of symbols and set of solution(s) use flag set=True
>>> solve([x**2 - 3, y - 1], set=True)
([x, y], {(-sqrt(3), 1), (sqrt(3), 1)})
But it has a lot of major issues like:
- It doesn't have a consistent output for various types of solutions & it needs to return a lot of types of solutions consistently:
- 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
x**2 + y**2 == 0
- Multivariate functions with non point solution
x**2 + y**2 == 1
- System of equations
x + y == 1
andx - y == 0
- Relational
x > 0
- And the most important case "We don't Know"
-
The input API is a mess, there are a lot of parameters. Many of them are not needed and they makes it hard for the user and the developers to work on solvers.
-
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.
solveset
was implemented as a GSOC Project in 2014 by Harsh Gupta and has a much cleaner input and output interface. The problem with solveset
is that it is not yet at par in functionality with the solve
function and cannot calculate solutions for many cases for which it raises Not Implemented Error
.
It solved many of the above listed issues like returning multiple and infinitely many solutions.For example:
For sin(x) = 0
, solveset
returns {2ā
nā
Ļ | n ā ā¤} āŖ {2ā
nā
Ļ + Ļ | n ā ā¤}
whereas solve
only returns [0, Ļ]
.
Also, solveset
returns a solution only when it can guarantee that it returns all solutions.
My project would be mainly concerned with:
-
Making a new transcendental equation solver (
transolve
) which will effectively usebivariate.py
and will be much more modular and extensible as compared to the present method (_tsolve
). Also, I would like to add aSet
output interface totransolve
which would enable it to be used bysolveset
to solve Transcendental equations much more effectively and quickly and also make the code base for the solvers module much more cleaner and efficient. -
Integrating helper solvers like
linsolve
,nonlinsolve
andsolve_decomposition
withsolveset
which will make it capable of solving a system of equations and for more than one variable. -
Building the set infrastructure to handle multidimensional ImageSet along with the development in solvers to ensure that the set functionality is maintained in
solveset
with the updated set infrastructure. -
Improve the trigonometric solver of
solveset
and handle trigonometric system of equations seperately innonlinsolve
so that it handles trigonometric and transcendental equations correctly all the time. This would also include some work on_solve_trig
and_invert
method if required, to close the issues #10217 and #10733 -
Change
solveset
appropriately to treat symbolic functions correctly in equations and solve those without an error.(As stated in issues #12239 and #12169) This will increase the power ofsolveset
so that it can be at par withsolve
in the future and maybe even replace it completely. -
Lastly, my goal would be also to edit
solveset
so that it gives solution if it exists in a much more simplified manner similar tosolve
for transcendental as well as as algebraic equations.(which would close issues like #12032)
I believe that successful implementation of my ideas will eventually help in closing issues #10006 and #8711 and hence make solveset
more powerful and comparable to solve
in functionality.
Progress & Discussions till now
solveset
was implemented as a GSoC project in 2014 by Harsh Gupta and it has since then grew in functionality. There has been a lot of work since:
Shekar Rajak worked on nonlinsolve
to solve non linear system of equations in solveset
(#PR 11111) which was merged into the main branch. He also worked on simplification of solutions for trigonometric equations for solveset
(PR #11188). I will do some more work as ImageSet
union doesn't work well for the simplification for all trigonometric solutions and also on nonlinsolve
so that it is able to handle transcendental equations correctly all the time.
Kshitij Saraogi worked on Intersection
for ImageSet
and other ranges(PR#11149, PR#11164). Also, he worked on function_range
to find range of a function free of singularities (removed using continuous_in
)in a given real interval range(PR #11224). I am planning to use these in my project as described in my project plan.
Moreover, the discussion on the mailing list, action plan for solvers, solveset
pull request and solveset
documentation have given me great insight to the current problem and I have developed a better approach to tackle them properly in the proposed transolve
and nonlinsolve
function to be implemented in solveset
.
Currently, solveset
returns a ConditionSet
even for simple cases of trigonometric equations like:
>>> solveset(cos(x)-x,x)
ConditionSet(x, Eq(-x + cos(x), 0), Complexes((-oo, oo) x (-oo, oo), False))
>>> solveset(x-exp(x),x)
ConditionSet(x, Eq(x - exp(x), 0), Complexes((-oo, oo) x (-oo, oo), False))
Such trivial cases need to be solved in solveset
as the solution for first is a real solution x ā 0.739085
and for the second one has 'No real solutions' as exp(x) > x
for all real values of x
. This behavior can be attributed to the fact that nonlinsolve
is not able to handle trigonometric and other types of transcendental equations as can be seen:
>>> nonlinsolve([x+exp(x)],x)
{(ConditionSet(x, Eq(x + exp(x), 0), Complexes((-oo, oo) x (-oo, oo), False)),)}
There also exist some issues with _solve_trig
and _invert
methods and need to be changed to make solutions for solveset
better and more simplified. For example:
>>> solveset(eq,domain=S.Reals)
ConditionSet(x, Eq(cos(sin(x) + 1) - 1, 0), (-oo, oo))
In this, as we see the nested trigonometric function cannot be solved by the solveset
using the present nonlinsolve
, _solve_trig
and _invert
methods.
solve_decomposition
has already been implemented up to great optimization and gives accurate results and will be very helpful in implementing the transolve
if the method of Rewriting and Decomposition can be applied to a given transcendental equation. Also, bivariate.py
module is very well implemented as a helper for solving transcendental equations and will also be very helpful in implementation of transolve
.
My Plan & Execution
As I stated earlier, my plan would mainly consist of:
-
Making a new transcendental equation solver (
transolve
). -
Integrating helper solvers in
solveset
includingtransolve
. -
Improving the trigonometric solver in
solveset
. -
Building the set infrastructure.
-
Changing
solveset
or helper functions so that the final solution is much more simplified just like insolve
.
This will be intended to close the issues: #10217, #10733, #12239, #12169, #12032, #10006 and #8711.
transolve
:
Making a new transcendental equation solver Transcendental Equation : A transcendental equation is an equation containing a transcendental function of the variable(s) being solved for. Such equations often do not have closed-form solutions. Examples include:
exp(x) = x
and sin(x) = x
Transcendental Function: A transcendental function is an analytic function that does not satisfy a polynomial equation, in contrast to an algebraic function. Formally, an analytic function Ę(z) of one real or complex variable z is transcendental if it is algebraically independent of that variable.[3] This can be extended to functions of several variables. Examples:
f(x) = sin(x)
and g(x) = x**(1/x)
I have classified transcendental functions into 3 basic categories:
- Trigonometric
- Exponential
- Logarithmic
and hence the helper solvers required to solve a transcendental equation are:
- Trigonometric solver (
_solve_trig
- Already present):
I am planning to use this only when the equation contains trigonometric or a piecewise combination of algebraic and trigonometric equations. For example:
sin(x) = 0
,sin(x) = cos(2*x)
andsin(x) = x
-
If the equation is purely trigonometric or piecewise combination of only algebraic and trigonometric functions then I propose to apply the
solve_decomposition
function to check whether the equation is solvable using the method of Rewriting and Decomposition. This method could possibly be applied also for finding solutions to nested purely trigonometric equations for which the current method insolveset
returnsConditionSet
.Examples:
cos(x)**2 + 1 - 2*cos(x)
,sin(x)**2 + 1 - 2*sin(x)
and(cos(sin(x)+1/2))-2
-
If a solution cannot be returned or this takes too much time to solve I would
simplify
the equation if possible using various identities and properties, convertsin
andcos
into their respective exponential forms and then pass onto the_invert
function which would then try and decompose this into smaller or sub-parts. From this point, I would try and solve the sub-parts independently and then later take union of variousImageSet
obtained as solutions to these sub-parts. -
If it is not purely trigonometric or piecewise combination of only algebraic and trigonometric functions then I would just try and
simplify
the trigonometric parts followed by_invert
and then solving the sub-problems independently and later take union of variousImageSet
obtained as solutions to these sub-parts.
So if no trigonometric term is found, the equation will not be passed onto this helper function.
Once this part is done, my next aim would be to try and make the solutions obtained as ImageSet
from Trigonometric Solver much more simplified if possible. For example, currently:
>>> solveset(sin(x),x)
{2ā
nā
Ļ | n ā ā¤} āŖ {2ā
nā
Ļ + Ļ | n ā ā¤}
whereas the solution for sin(x) = 0
can be written in a much simplified form as {nā
Ļ| n ā ā¤}
Similarly, in this example:
>>> solveset(cos(x),x)
ā§ Ļ ā« ā§ 3ā
Ļ ā«
āØ2ā
nā
Ļ + ā | n ā ā¤ā¬ āŖ āØ2ā
nā
Ļ + āāā | n ā ā¤ā¬
ā© 2 ā ā© 2 ā
whereas the solution for cos(x) = 0
can be written in much simplified form as:
ā§ Ļ ā«
āØnā
Ļ - ā | n ā ā¤ā¬
ā© 2 ā
- Exponential / Logarithmic solver :
I am considering a single case for equations containing either exponential or logarithmic or both functions because one can easily be converted to another.
I intend to create this helper function forsolveset
by leveraging the power of thebivariate
module. This solver will firstly collect and convert the non-trivial exponential forms into logarithmic ones and then use the_invert
function to decompose into sub-parts which then can be solved independently.
After decomposition I would first use thebivariate
module to recognize whether any sub-part is any of Lambert forms and solve them accordingly using various helper functions inbivariate
module.
--
Currently,solveset
either partially handles such types of equations or returnsConditionSet
as shown by the following examples:
>>> solveset(4**x - 16,x)
ConditionSet(x, Eq(4**x - 16, 0), Complexes((-oo, oo) x (-oo, oo), False))
>>> solveset(3**x - 2**x - 1,x)
ConditionSet(x, Eq(-2**x + 3**x - 1, 0), Complexes((-oo, oo) x (-oo, oo), False))
The correct answer for the examples can be calculated in very simple manner and are given by x = 2
and x = 1
. After my implementation of transolve
these errors are expected to be resolved.
Timeline
The project requires a lot of thought and effort and will take a lot of time to complete but will definitely extend the functionality of solveset
and I am pretty confident that I can complete it well before the final submissions.
I will be having my end-semester examination from 20th April to 28th April and hence will start working for the project much well in advance to the start of Community Bonding.
Community Bonding Period - (5th - 30th May, 2017):
-
I will start the Pre-Project planning and start studying the code base in a much detailed, well-planned and well-documented manner so that I am able to understand the functioning of various modules properly directly or indirectly related to my project.
-
Start discussions with the mentors and other people of the community to come up with an efficient strategy to implement the plan and also make suitable changes to proposed execution if it doesn't satisfy the mentor or the organization.
-
Searching for various other problems and issues with the current
solve
module and their implementation and making a detailed list of the same which will eventually help in the extension ofsolveset
in a much more cleaner and efficient way. -
Writing detailed test cases that currently don't produce the correct output for
solveset
and understanding the reasons for the same. This will help in rigorous testing of any updates insolveset
regularly.
Week 1 and 2 - (30th May - 13th June):
-
Initiation of implementation of
transolve
by studying the function_tsolve
properly and analyzing why it is so effective. -
Implementation of
transolve
for the simpler cases which include purely logarithmic and exponential transcendental equations usingsolve_decomposition
and_invert
helper functions and various approximation techniques(if required) as explained in execution of project. -
Documentation of the analysis for
_tsolve
and the basic implementation oftransolve
, writing test cases for work done till now and submission of a PR for review of work done. -
Doing all this, while keeping in mind from the beginning that the code must be more modular and extensible as compared to
_tsolve
and also that it should include the set output interface. -
Fixing bugs and issues due the previous PR.
Week 3,4 and 5 - (14th June - 4th July):
-
Incorporating various special values and identities of
Lambert W
function as base cases to improve the performance oftransolve
for functions in any Lambert form. -
Implementation of
transolve
for equations that are in a Lambert form using the power ofbivariate
module and the identities and special values incorporated earlier. -
Documentation of work done till now and writing test cases for equations that are in a Lambert form. Submission of a PR for review after major work for logarithmic/exponential solver is complete.
-
Fixing issues and bugs in the submitted PR.
-
Improvement in
_solve_trig
and_invert
helper functions which would fix various issues like incorrect solutions for nested trigonometric functions (Issue #10217 and Issue #10733). This would use helper functions likesolve_decomposition
for simplification of the equation, various approximation algorithms(when the solution is real) and also use some ideas from thesolve
function to tackle trigonometric transcendental equations.
Week 6 and 7 - (5th - 18th July, 2017):
-
Implementation of
Trigonometric Solver
for purely trigonometric transcendental equations using updated_solve_trig
andsolve_decomposition
helper functions as described in the execution of my plan. -
Implementation for more complex cases of trigonometric transcendental equations which may include piecewise combination of various trigonometric, algebraic and exponential functions using
simplify
followed by_invert
and then takingImageSet
Union for solutions of sub-parts. -
Improve trigonometric solver for
solveset
to handle trigonometric system of equations separately innonlinsolve
. Also, make suitable changes innonlinsolve
to handle transcendental equations in a better way using the new transcendental solvers. -
Testing and documentation of the completed trigonometric solver and submitting a PR for the same for review.
Week 8 and 9 - (19th July - 1st August):
-
Fixing bugs and issues pending till now.
-
Building up the set infrastructure to handle multidimensional
ImageSet
and also improve theImageSet Union
operation so that the output is consistently correct and simplified. This will solve Issue #12032 and other similar issues. -
Writing tests and documentation for multidimensional
ImageSet
and submit a PR for review.
Week 10 and 11 - (1st - 14th August, 2017):
-
Fixing bugs and issues due to the updated
ImageSet
and compatibilty issues that may arise. -
Changes in solveset to treat symbolic functions correctly to solve the issues: #12239 and #12169.
-
Simplification of
ImageSet
output so that the solution is displayed in a much less complicated manner similar tosolve
to solve the issues like #12032 -
Writing tests and documentation for the updates.
Week 12 and 13 - (15th - 28th August, 2017):
-
Finishing up with any work left which involving coding or any changes in code.
-
Writing documentation and project summary.
-
Final PR submission and attempt to merge without conflicts.