GSoC 2017 Application Gaurav Dhingra: Risch algorithm for symbolic integration - sympy/sympy GitHub Wiki
Name: Gaurav Dhingra
University: Indian Institute of Technology Roorkee
Email: gauravdhingra.gxyd [at] gmail.com
GitHub user name: gxyd
IRC Handle: gxyd [at] freenode.net
Blog: https://gxyd.github.io
Time Zone: IST (UTC +5:30)
Hello, I am Gaurav Dhingra a 4th year undergraduate student of Applied Mathematics at IIT Roorkee, India. I work on Ubuntu 14.04.5 LTS with vim as my primary text editor. I do my work with vim since it allows me work quickly with the code when added with vim-extensions using Vundle. I have been programming for 3 years now, I am proficient in Python, C++. I started using Python in parallel with contributing to SymPy. Python's list comprehension is a cool feature missing in other programming languages. I contributed to Pi-Producing Program which uses SymPy to generated "PI" in different ways. I like Python since as a math major Python allows me to convert mathematical ideas into code without much programming langauge barriers. Editing wikipedia articles is something that i also like so I have often edited the SymPy wikipedia article quite a few times.
By now, I have used quite a few computer algebra systems including GAP, Axiom, Maple and even after being a commiter of SymPy for than a year, I can say that the printing system of SymPy is something that is missing in other computer algebra system.
>>> print(latex(Integral(x**2/(1 + x**4), (x, 0, oo))))
\int_{0}^{\infty} \frac{x^2}{1 + x^4} dx
My proposal is to improve the Symbolic integrator of SymPy.
SymPy's current integrator module does a pretty good job in computing whatever is thrown at it. The main algorithm used in SymPy for symbolic integration is the Risch algorithm, though there are others as well like Risch-Norman algorithm, table look up. The aim of my project is to complete the transcendental function integration of Risch algorithm that includes completing Chetna's work done in GSoC 2013 on transcendental functions integration [1], tying the loose end of previous year's GSoC and completing the purely algebraic function integration.
- Completing the previous remaining work.
Complete the pull request #2380.
- Don't hardcode the value of a in the functions in cds.py. And the input should be a, not sqrt(a), (so, e.g., the input should be -1, not sqrt(-1)).
- is_deriv returning logs is wrong.
- Make sure all tests pass (check Travis).
Kalevi had created a pull request #11761 [3] on recursive call to the param_rischDE in the function 'prde_no_cancel_b_small'.
There are a plenty of #TODO's and NotImplementedError in the integration module:
Parametric logarithmic derivative [4]: section: 7.3, the complete solution is provided by structure theorem that is not implemented. Though a heuristic method 'parametric_log_deriv_heu' is implemented which still is not complete and also requires does need writing of test cases, so if this heuristic fails, the structure theorem approach will need to be used. There doesn't seem to be any pseudo-code available for this.
Passing information for why integral was non-elementary: see line 685 in `risch.py`. For this we could use a class-level variable named `message` in class associated with class `Integral` which will be set to appropriate str value. So instead of only raising `NonElementaryIntegralException` first message is set a value. Since each place in the code that raises `NonElementaryIntegralException` has a specific reason in the algorithm why the integral must be non-elementary if the code reaches that point.
For the algebraic function integration, a description is given on Trager's page 13 to obtain canonical forms for the ones which can't be evaluated as well as for those which are not integrable(non-elementary).
- See prde.py line number 456, implement Parametric Risch DE.
(a). theta_i = log(z), where z \in K(x, theta1, theta2, ..., theta_(i-1)), i.e. theta_i is a written as a logarithm of field extension of theta1, theta2, ..., theta(i-1).
(b). theta_i = z = exp(y) for y \in k_i i.e. theta_i is written as an exponential of field extension of theta1, theta2, ..., theta(i-1).
(c). theta_i = v = tan(u) for u \in k_i i.e. theta_i is written as a tangent of field extension of theta1, theta2, ..., theta(i-1).
(d). theta_i = u = atan(v) for v \in k_i i.e. theta_i is written as a tangent of field extension of theta1, theta2, ..., theta(i-1).
- Implement the integration of algebraic extensions, currently only transcendental extensions are implemented. Read conversations after message [6]
Computing Integral basis: Algorithm for computing integral basis for our function field, though computing it is an ongoing research and computing it is no harder than computing Pusieux expansion.
A class named `IntegralBasis(f, x, y)` Returns the integral basis of the algebraic function field of.
The `.integral_basis` method of `IntegralBasis`
- Parameters*: `f`: sympy.Expr
- Returns*: list, Expr i.e A list of rational functions representing an integral basis.
This will help in: This will determine the nature of poles of an algebraic function.
How are we going to do that? Present as chapter 2 in [9]. Anything necessary to complete this? This algorithm constructs the algebraic part of answer by a generalization of Hermite's reduction. So going through the Hermite reduction present in Bronstein [10] will help.
Algorithm to find absolutely irreducible factors of multivariate polynomials
Algorithm finding the genus of a curve
What will happen in case the problem is not integrable? Even when the problem is not integrable it will be reduced to a simpler version of the original problem.
A good resource for integration of algebraic functions is [8].
Considering my last year's experience with GSoC, we didn't followed much according to the time (for good reasons). But still having a time-line helps in acting as a self check.
- Will go through and complete the pull request #2380 on Coupled Differential System.
- Complete the Parametric risch differential equation PR #11761.
- Support for trigonometric extensions.
- Purely algebraic function integration.
- Complete the
Last summer also I worked on SymPy for Google Summer of Code, which was my first experience with open source, now its been exactly 2 years since my first commit got merged in SymPy. My project was to extend implementations in Computational Group Theory, and it was successful. I decided to continue as a developer of SymPy. I blog at https://gxyd.github.io, which was also my blog for last summer Google Summer of Code project.
Also I am learning to use PuDB since that will make learning of algorithm a little easier.
I will devote 30+ hours/week (updated weekly hour work, see faq). My summer break starts on 1st May. I can use this time to get a head start into the tasks at hand too. Also, I can efficiently use the time before the summers to gather all the necessary information and details on my project, so I can begin work without any delays, so I will try to work from there onwards too.
We have a gitter channel on [7] which we plan to continue using, though time for communication between me and Aaron (probably he will be mentoring) since of time difference, but with a secondary mentor like Kalevi(his knowledge is always helpful), I think we can get things done in a better way. Since of my last GSoC project I have some algorithmic exposure to abstract algebra.
I have gone through the Lazard-Rioboo-Trager algorithm (since because complete Risch algorithm is a generalization of this) and chapter 5 of Manuel Bronstein [10].
[1] #2380, #2184, #2077, #2034
[2] Risch algorithm for symbolic integration discussion thread
[3] https://github.com/sympy/sympy/pull/11761
[4] https://github.com/sympy/sympy/blob/master/sympy/integrals/prde.py#L566
[5] ISSAC '89 Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation Pages 207-211
[6] https://gitter.im/jksuom/sympy?at=58d035cffe6a638b1ae6f2b4
[7] https://gitter.im/jksuom/sympy
[8] James Harold Davenport, On the Integration of Algebraic Functions
[9] Integration of Algebraic Functions by Barry Marshall Trager
[10] Manuel Bronstein Symbolic Integration 1 Transcendental Functions