GSoC 2013 Application Chetna Gupta: Risch algorithm for symbolic integration - sympy/sympy GitHub Wiki

This proposal is still in progress

Personal Details

Name: Chetna Gupta Email: [email protected] IRC: chetna on freenode Skype: chetna.gupta3 Github: cheatiiit

Backgound

I am a second year Computer Science student at International Institute of Information and Technology, Hyderabad, India. I am planning to pursue my honors in Visual Image processing. I am a Microsft Windows 8 Official App developer and have been one amongst the winning teams of Microsoft Acad Accelerator . Being a member of the Open Source Development Group at my college and after participating in various hackathons I realized that open source is based on scratching a developer's personal itch. Complex data signal analysis, integrating filters with signals to recover data etc, as would be required for my honors motivated me to look for python based CAS and indeed I started looking into sympy’s codebase . Maths has always been not only a field of knowledge but also encouragement for me. I am quite comfortable with Linear Algebra and Abstract Algebra.

Coding

I've done coding in several high-level languages (C, C++, C#, Python, Java); What I like about Python, as a mathematician, is the simplicity and readability of the language which allow for what I find to be very elegant programs. For over two years now I've been coding on a Linux workstation. I cannot say I'm considerably fluent in Python but I see my level somewhere around intermediate. I have written various scripts to analyze data in various fields of my interest, this includes use of python to interpret dynamic nature of signals mostly Wi-Fi- Access Points. building backend for Search engines , data-file parsers, python web-crawler, using python based web development softwares like web2py and also developing game using n-curses library as a course project.

I have been using svn and had heard of git before, but I started using it because of my involvement in the sympy project. I'm still learning the little tricks, but now that I've submitted some of the patches enhancing the code under the integral module which make me feel more confident about using it.

Contributions to Sympy

My contributions to Sympy are as follows:

Currently working on:

Merged pull requests:

The Project

Timeline

As I have already started following the text for implementation and improvisation of risch algorithm, I plan to immediately start working on the same.

  • Week 1-2 Recognizing derivatives, log derivatives , log derivatives in k radical along with test cases and also the unimplemented sub-algorithms of Risch Differential Equations.
  • Week 3 Implementation of Cancellation Algorithm for the Liouvillian Case
  • Week 4 Consideration of Non-Linear Cases in Parametric Risch Differntial Equation
  • Week 5 Solution for Hyper-tangent Cases by using Cancellation Algorithm
  • Week 6 Would start looking into code for implementation of coupled differential equation and would solve CDS for the primitive cases, more sophisticated testing and benchmark
  • Week 7-8 (Mid-term Evaluation) Solution of CDE for hypertangent and exponential cases with test cases
  • Week 9 Implementation of non-linear cases for Coupled Differential System
  • Week 10 Would review all the pull requests and would add more complex test cases for each
  • Week 11 Structure theorem for cases other than linear & exponential and solving parametric logarithmic derivative problem
  • Week 12 Extending Limited integration Algorithm, Adding complex test Cases for all the cases
  • Week 13 Look back at the entire code and make improvements & stylistic changes if necessary; more sophisticated testing, benchmarks (if not done already); add details to documentation
  • Week 14 Final Evaluation

Implementation Details

Implementation of methods to recognize derivatives , logarithmic derivatives, logarithmic derivatives k(t) radical

A code-block for recognizing derivatives, log derivatives and log derivatives k radical, "integrals" module would enable us to implement most of the algorithms for the Risch differential Equation which have been raising a NonImplementedErrors.

Examples from the code

  • Special_denom in integrals/rde.py :

Theory Planned

  1. Recognizing Derivatives:

I have already started working on this by including methods like:

Although these two approaches would solve most of the cases but still it is not an alternative to the normal method of using Hermite Reduction and calculating integral(returning True if an integral is found, False otherwise) therefore if none of them prove that the function is a derivative of a rational function then we shift to the last available choice of hermite reduction. I am mostly done with the laurent series approach but still need to add complex test cases and code the 'Marik Criteria' and 'Hermite Reduction Method' so that we can get a valid result for more general functions. As a result alot still needs to be done in this section. As there is no psudeo code present for solving this in [1] or any other on-line references, therefore I would have to write more unit-testing test cases to check and verify each line of the code. This would require me to exhaust all possibilities where the above may fail. I intend to put laborious calculations to get this through as not much examples are available to solve this.

I have also included test cases to recheck and verify each and every line of the code. Therefore there is nothing much left to do for this part. But as some of the Risch Differential Equation algorithms have sub-parts which particularly depend on the recognizability of a function to be a log derivative, I plan to complete all such possible sub-parts using this method. Hence exhausting and completing the sub-algorithms that haven't been implemented yet from Chapter 6 of [1]

Implementation and Improvisation of Parametric Risch Differential Equations

To solve Parametric Differential Equations currently the only cases implemented in integral module for equations of the form Dq + bq = Sum(i,1,m) ciqi are as follows:

  • D = d/dt or deg(b) > max(0,delta(t)-1)
  • deg(b) < delta(t) - 1 or delt(t) >=2

We still need non-cancellation algorithm for cases of the form delta(t)>=2 and degree(b) - delta(t)-1 as well as cancellation algorithms for

  • Liouvillian Cases -> D != d/dt and deg(t)<=1
  • Nonlinear Cases -> delta(t) >=2 and degree(b) =delta(t)-1 and lc(b) = n*lambda(t)
  • Hypertangent Cases -> Dt/(t^2+1) = eta in k such that delta(t)=2

Implementation of Coupled Differential System

As there is no method to address a solution for coupled differential system, I plan to write various cancellation algorithms which would help in extending Coupled Differential Systems to a coupled system of real and imaginary part of risch differential equations. This would enable us to find solutions of the form (say) (y1,y2) where y1,y2,y satisfy #####Dy + (f1 + f2*sqrt(a))= (g1 + g2*sqrt(a))

  • y = y1 + sqrt(a)*y2
  • y belongs to K(sqrt(a))
  • y1, y2 belongs to K
  • sqrt(a) does to belongs to K for a given Differential Extension K (a = -1 being a specific case for the above conditions)
Theory Planned

Since coupled differential systems are generated by integration algorithms only when sqrt(-1) [in general a] does not belong to K, therefore inorder to find a solution for y belonging to K(sqrt(-1)) of Dy + (f1 + f2sqrt(-1))y = g1 + g2sqrt(-1) ---Eq1 I would consider real (say y1 ) and imaginary (say y2) parts of y. Hence y = y1 +y2sqrt(-1) putting this in Eq1 we get D(y1+sqrt(y2)) + (f1+f2(sqrt(-1))(y1+sqrt(-1)y2) = g1 + g2sqrt(-1) ---Eq2 Dy1 + sqrt(-1)Dy2 + f1y1 - f2y2 +sqrt(-1)(f1y2+f2y1) = g1 + g2(sqrt(-1)) --Eq3 Separating Real and imaginary parts of the Eq2 we get Dy1 + f1y1 - f2y2 = g1 ---Eq4 Dy2 + f1y2 + f2y1 = g2 ---Eq5

Since {1,sqrt(-1)} is a vector space basis for K(sqrt(-1)) over K, therefore if f1,f2,g1 and g2 are in K(t) then y1+ sqrt(-1)y2 is a definite solution to Eq1. In order to compute the above let f = f1 + f2sqrt(a), g = g1 + g2sqrt(a) So Eq3 looks like: Dy + fy = g Eq--6 Applying Rothsien SPDE Algorithm to the above equation, I intend to prove that either there is no solution for y in k(sqrt(a)(t) or there exist b, c, d, alpha, beta in k(sqrt(a)[t] such that if a solution exists then y is of the form y = (alpha*q + beta)/d where q in k(sqrt(a))[t] is a solution of Dq + bq = c. Depending on the value of b we can check if the result from SPDE algorithm falls into non-cancellation cases ie:

  • If degree(b) is large enough b != 0 and D = d/dt or deg(b) > max(0,delta(t)-1)
  • If deg(q) > 0, deg(b) < delta(t) - 1, and either delta(t) >= 2 or D = d/dt,
  • If delta(t) > 2, deg(b) = delta(t) - 1, deg(g) > 0 and deg(g) != -lc(b)/lambda(t)

If any of the above conditions are satisfied then we can apply the corresponding no-cancellation algorithms to the reduced equation Dq + bq = c since they do not generate any recursive problem over k(sqrt(a)). Thus, in the non-cancellation cases, we can either prove that there is has no solution in k(sqrt(a))(t), or compute such a solution. Apart from non-cancellaton cases CDS should also handle cancellation cases that is:

  • delta(t) < 1, b in k(sqrt(a)) and D != d/dt,
  • delta(t) >= 2, deg(b) = delta(t) - 1, and deg(q) = -lc(b)/lambda(t).

Implementation of Structure theorem

Note, some of these are straightforward to implement. For example, After going through [1] I found that it may not take much time in implementation of methods to recognize derivatives or logarithmic derivatives . While others such as Structure theorem and CDE will require more work to ensure that they catch all the types of possibilities that really fit their form. For this reason, it is possible that I may spend more time on one than I anticipated.

##Logistics / Disclaimers

I have no plans other than traveling back home in the beginning of May , though this won’t affect my productivity. I would be back in college by Mid-May for next 3 months. Inorder to accomplish the opportunity I seek through this project, I would dedicate a whole-hearted 40 hours a week to work completely according to the timeline. I am mostly a self taught coder and learner but as most of the implementation left does not have a psudeo code or examples, though i would refer to various possible research papers, I would need some help to structure my work accordingly. I plan to an active sympy developer even after GSoC time-period and would continue the work I would undertake this summer

References