GSoC 2017 Application Gaurav Dhingra: Risch algorithm for symbolic integration

Gaurav Dhingra edited this page Mar 31, 2017 · 3 revisions

Table of Contents

About Me

Name and Contact info

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)

Personal Background

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

Contributions to SymPy

The Project

The Problem and Motivation

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.

Implementation Details

  • Completing the previous remaining work.

Chetna's 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's work

Kalevi had created a pull request #11761 [3] on recursive call to the param_rischDE in the function 'prde_no_cancel_b_small'.

Completing transcendental function integration

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.
Support for trigonometric extensions: Currently, part of transcendental case is implemented, meaning elementary integrals containing exponentials, logarithms but the trigonometry still needs to be implemented. Support for trigonometric extensions, see `risch.py` line number 232. Simplification of real elementary functions [5]: to find all the algebraic relationships among a given set of real elementary functions, there is a description of this in paper [5] with mathematical examples but no pseudo code. This provides a better solution over converting the real elementary functions to logarithms and exponentials and then using them computing the integral. The initial step of the algorithm requires building of a tower, which is already there in `DifferentialExtension` object. See if the given expression has a non-real complex constant and if it does then we will have to shift to its "complex" version. We have 4 cases in which the algorithm is divided into:

(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).

Integration of Algebraic Functions

  • Implement the integration of algebraic extensions, currently only transcendental extensions are implemented. Read conversations after message [6]
There are two good description for the implementation of Algebraic function integration, first being the one by James H Davenport and second one being by Trager. Davenport's proposed implementation has been superseded by Trager's improvements. Davenport's implementation uses Puiseux series. Puiseux series, in particular, are not needed for Trager's implementation. They are inconvenient because of the algebraic extensions the base field that are necessary in the computations but not in the final results. Risch makes extensive use of Puiseux series which leads to operate in an extension field of much higher degree for his intermediate computations.

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
`x`: Symbol `y`: Symbol
  • Returns*: list, Expr i.e A list of rational functions representing an integral basis.
Computing singularities: A module for computing the singular points of a complex plane algebraic curve including their multiplicities, branching numbers, multiplicities, and delta invariants.

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

Proposed Time-line

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.

Community Bonding Period (5 May - 30 May)

Week 1, 2

  • Will go through and complete the pull request #2380 on Coupled Differential System.
  • Complete the Parametric risch differential equation PR #11761.

Week 3, 4

  • Support for trigonometric extensions.

Week 5 to 13

  • Purely algebraic function integration.
  • Complete the
Week-wise division of work.

How do I fit in?

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

References

[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

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.