GSoC 2016 Application Shravan Patel: ODE

#Implementing new methods to solve ODE ##Personal Details Name: Shravan Patel

University: Indian Institute of Technology, Mandi

Email: [email protected]

Github: shravanpatel5

##Background and Programming Skills I am Shravan Patel. I am currently pursuing second year B.Tech in Computer Science and Engineering at Indian Institute of Technology, Mandi. My field of interest include Competitive Programming, Mathematics and Electronics. Few months ago, I heard my senior telling "Competitive Programming is not everything, you should contribute to Open Source Softwares". That increased my interest in Open Source Software Development and I started contributing in Open Source Softwares.

I code in C, C++ and Python. I make websites using PHP, HTML, CSS and JavaScript. I have taken course of Ordinary Differential Equations in my 1st semester and worked good in it. I use python since my first semester. I am intermediate in Python. Code in python is 5 times shorter than code in any other language. That's very cool. In built Dictionary, no memory management, too many standard libraries, For..else syntax and many other things that I liked most.

I started finding lack of any feature in sympy few weeks ago. I was surprised after knowing that almost all functions of all areas of mathematics are implemented. I installed it on my laptop and started using it. I liked Sympy's integration most. I only had to type an equation and i got an answer.

>>>integrate(sec(x)-tan(x)*tan(x))

x − log(sin(x)−1)/2 + log(sin(x)+1)/2 − sin(x)/cos(x)

##Contributions to sympy

Unmerged : #10904

Added some functions for efficiently finding the maximum power of a number x that divides a factorial of y without calculating factorial of y
e.g. Finding trailing zeros in 10000 factorial

>>>max_pow_in_factorial(10000,10)

2499

##Project Idea

###Abstract The implementation of the current ODE solver in sympy was started by Aaron Meurer as his GSoC Project in 2009. Currently, SymPy's ODE solver has many methods to solve differential equations. But there are many methods that are not implemented. My project proposal would be dealing with the implementation of these three features.

Implementation of a function for separation ansatz

At present, ODE module have a method to solve differential equations which are separable. I would like to make a simple and very fast function which will find out whether an ordinary differential equation is separable or not.
Solving Differential Equations in Terms of Bessel Functions

Ode module have a method to solve second order differential equations which are in Liouville form. Bessel equation and Liouville form are similar. This project is aimed to develop a method that combines generalized exponents to solve second order differential equations in terms of Bessel functions.
Solving second order ODE using Lie Groups and symmetric method

In GSoC 2013, Manoj Kumar implemented the method to solve first order differential equations using Lie groups. At the end of this project, Ode module would be able to solve second order differential equations using Lie group.

###Inspiration In beginning, I was finding a organization which require C/C++/Python and Mathematics. I got few such organizations. Because of too many good and interesting ideas related to mathematics, I chose SymPy. As I had taken a course on ODE, I got interest in this project proposal idea.

###Theory

Implementation of a function for separation ansatz

Suppose dy/dx = f(x,y). If f(x,y) is separable as f(x,y) = φ(x)*ψ(y) we can solve it using ode_saperable(). There is a very fast method to check whether f(x,y) is separable or not.

(1) Choose any (x0, y0) such that f(x0, y0) != 0.
(2) Construct the functions φ(x) = f(x,y0)/f(x0,y0) and ψ(y) = f(x0, y).
(3) The equation is separable if and only if f(x, y) = φ(x)*ψ(y).

Solving Differential Equations in Terms of Bessel Functions

The solutions of the differential equation x^2(d^2 y)/(dx^2)+x(dy)/(dx)+(x^2-n^2)y=0 are called Bessel functions. Jν(x) and Yν(x) are called Bessel functions of first and second kind, respectively. For a Bessel function Z_n(x), Z_(n+1)+Z_(n-1) = ((2n)/x)*Z_n and Z_(n+1)-Z_(n-1) = -2(d Z_n)/(dx).

Algorithm :

Suppose Lin is our ode. We can compute the singularities of Lin by factoring the leading coefficient of Lin and the denominators of the other coefficients into linear factors.
For each singularity s, we compute ds = ∆(Lin, s). Isolate exp-apparent points with ds ∈ Z and differ between exp-regular singularities Sreg with ds ∈ C and exp-irregular singularities Sirr with ds ∈ C[ts−1]\C .
We can use the exponent differences ds for s ∈ Sirr to compute candidates F for the parameter f up to a constant c ∈ k.
In all cases but the integer case we know at least one zero of f by picking some s0 ∈ Sreg. So we can also compute the missing constant c for each ˜f ∈ F.
The set N is a set of candidates for ν. When not in the integer case, we compute this finite set. N might depend on f.
For each f ∈ F and each ν ∈ N compute M = M(ν, f).
For each M decide if gauge transformation is possible or not. If yes then solve it by a method present in paper.

Solving second order ODE using Lie Groups and symmetric method

In short, in this method we will convert second order differential equation to the canonical system in which solution is independent of x and y. Then we will find the solution of the equation in canonical system and then convert it into original one.

Algorithm :

Consider a second order differenetial eqation d^2 y/dx^2 = h(x,y,dy/dx).
Find the infinitesimals ξ and η by solving this partial differential equation :

(2*y1*(∂^2n/∂y*∂y1) + 2*(∂^2n/∂x*∂y1) - 3*y1*(∂ξ/∂y) - 2*(∂ξ/∂x) - 2*y1*(∂^2ξ/∂x*∂y1) + (∂η/∂y) - 2*y1*y1(∂^2ξ/∂y*∂y1))h + (-y1(∂η/∂y) + y1*y1(∂ξ/∂y) + y1(∂ξ/∂x) - (∂η/∂x))*(∂h/∂y1) + (∂^2η/∂x^2) + (∂^2η/∂y^2)*y1*y1 + ( y1(∂η/∂y1) + y1*y1(∂ξ/∂y1) - η )*(∂h/∂y) + ( (∂^2η/∂y1^2) - y1(∂^2ξ/∂y1^2) - 2(∂ξ/∂y1) )*h*h + ( (∂η/∂y1) - y1(∂ξ/∂y1) -ξ )*(∂h/∂x) - (∂^2ξ/∂y^2)*(y1^3) - 2*(∂^2ξ/∂y*∂x)*y1*y1 + 2(∂^2n/∂y*∂x)y1 - y1(∂^2ξ/∂x^2) = 0

Find r and s. The whole method is present in Cheb-Terrab's paper.
Convert the equation into canonical co-ordinate system. This would reduce it to the separable form, which can be solved using the separable method.
Re-substitute r(x,y) and s(x,y) in terms of x and y. We would get the solution in the original co-ordinate system.

###Implementation

Implementation of a function for separation ansatz

First algorithm is to find x0 and y0 in constant order for which f(x0,y0) is not zero. After that φ(x) and ψ(y) can be easily calculated and then by comparing f(x,y) to φ(x)*ψ(y) function will return false or φ(x) and ψ(y) with true.

Solving Differential Equations in Terms of Bessel Functions

First algorithm would be finding singularities of Lin as mentioned in theory.
In second set of algorithms, I would find a set of exp-irregular singularities Sirr with ds ∈ C[ts−1]\C
In third algorithm, Candidates of F would be calculated.
forth set of algorithms would be computing the missing constant c for each ˜f ∈ F as mentioned in theory part.
fifth algorithm would be finding set N.
In sixth set of algorithms, M would be calculated and for each M it would be decided if gauge transformation is possible or not.
In last algorithm, Ode would be solved.

Solving second order ODE using Lie Groups and symmetric method

First and main set of algorithms would be finding ξ and η from the equation. After that our work is easy.
In second set of algorithms, I would find r and s using method present in the Cheb-Terrab's paper.
third set of algorithms would be converting the equation into canonical form. After that we can simplify it and solve by hint saperable.
In forth set of algorithms I would re-substitute r(x,y) and s(x,y) in terms of x and yto get solution of ode in original coordinate system.
User Interface would be like this :

>>> classify_ode(ode)

('Liegroup2')

>>>infinitesimals2(ode) 

[ξ=0,η=x],[ξ=x,η=y],[ξ=x*x,η=y*x]

>>>dsolve(ode,f(x),hint='liegroup2')

solution of ode

##Timeline

Befor April 22

To familiarize myself completely with SymPy's ODE module's functionality and architecture
Deep study of the "Solving Differential Equations in Terms of Bessel Functions"
Deep study of the Lie Group method for solving second order ODE

Community bonding period(April 22 - May 22)

The main focus in this period would be creating the efficient algorithms.
During this period I will remain in constant touch with my mentor. I will remain active on IRC and Mailling lists to discuss and finalize on the modifications (if any) that needs to be on existing schemas and design of new schemas. Thus with the help of my mentor I will become absolutely clear about my future goals.
If I would get extra time, I would start coding in this phase.

Week 1 - Week 3 (May 23 - June 13)

Code the algorithms of separation ansatz.
Pull request of implemented algorithms.

Week 4 - Week 5 (June 13 - June 27)

Code first and second set of algorithms of solving ode in term of Bessel Functions.
After implementing each set of algorithms, there would be pull request.

Midterm Evaluation

Fix bugs if any

Week 6 - Week 7 (June 27 - July 11)

Code third, forth and fifth set of algorithms of solving ode in term of Bessel Functions.
Pull request of implemented algorithms.

Week 8 - Week 9 (July 11 - July 25)

Code sixth and seventh set of algorithms of solving ode in term of Bessel Functions.
Pull request of this two algorithms.
Code first set of algorithms of solving second order ODE using Lie Groups.
Pull request of this algorithm.

Week 10 - Week 11 (July 25 - August 8)

Code second,third and forth set of algorithms of solving second order ODE using Lie Groups.
After implementing each set of algorithms, there would be pull request.

Week 12 (August 8 - August 16)

Write documentation and fix bugs that may arise

Week 13 (August 16 - August 24)

Final Evaluation

Notes :-

I have final exams during week 2 and week3. So I would be able to devote 15-25 hours per week in the period of exam. After week 3 I would be able to devote 40-50 hours per week. I have no other project or internship for the summer. My next semester will start around 10 August. So there won't be any clash with GSoC.
Though accepted students proposals will be announced on 22 April, I will read the related PDFs very deeply before April 22 because if I will get selected, it would be very helpful to me in GSoC but in case I won't, it would be useful to me somewhere.

##References

GSoC 2016 Application Shravan Patel: ODE - sympy/sympy GitHub Wiki

⚠️ GitHub.com Fallback ⚠️

GSoC 2016 Application Shravan Patel: ODE - sympy/sympy GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️