Skip to content

GSoC 2013 Application Chetna Gupta: Risch algorithm for symbolic integration

Jump to bottom Edit New page
Sean Vig edited this page Jul 18, 2013 · 1 revision

This proposal is still in progress

Personal Details

Name: Chetna Gupta
Email: cheta.gup@gmail.com
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:


Implementing Method for recognizing derivatives , logarithmic derivatives for rational functions Section 5.12 from [1] which has been bottlenecking most of the other unimplemented algorithms

Merged pull requests:


Changed SPDE from recursive to iterative (Prevents RuntimeError when called recursively by functions like rischDE, paramrischDE) * https://github.com/sympy/sympy/pull/1957:
Changed integrate_primitive_polynomial from recursive to iterative (Prevents RuntimeError: maximum recursion depth exceeded for test-cases with large powers eg risch_integrate((log(x)+1)**1001) * https://github.com/sympy/sympy/pull/1948 :
Enhanced Hermite Algorithm from quadratic version to Mack's Linear version (Reduced time complexity from n**2 to n-1) * https://github.com/sympy/sympy/pull/1917 :
Implemented risch_integrate for trigonometric, inverse trigonometric and hyperbolic functions (Raised NonImplementedError earlier) * https://github.com/sympy/sympy/pull/1906 :
Optimized number of permutations of mappings in heurisch (Reduced order from n! to n-1!)

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 :

This method though works for primitive, exponential and base cases but it fails to solve hypertangent cases raising a `NotImplementedError("Tangent case not implemented yet for " "RDE special_denom().")` because of unavailability of algorithm to check if there exist a log derivative of a function (say) `B = dv/v for some v in K*`

Theory Planned

  1. Recognizing Derivatives:

In order to recognize if a given rational function (say) F is a derivative of a rational function without actually computing the integral of F, I plan to use a couple of criterion as follows:
-- **Laurent Series Method**:
For a give function F let A,D be the numerator and denomintor of F respectively where A,D belong to K(x) with D monic and nonzero, `gcd(A, D) = 1`, If `D = D1,D2...Dn` is squarefree factorization of D. Then, using only rational operations over K, for each Di (i varies from 1 to n) I compute `Hij` belonging to K[x] for `1 <= j <= i <= n` such that the partial fraction decomposition of `A/D` is `A/D = P + Sum(i,1,n) Sum(a,Di(a)=0) (Hii(a)/(x-a)^i + ... + Hi1(a)/(x-a))` After computing Hi1 for each Di,we write Di as `Di = GiEi` where `Gj = gcd(Hi1, Di)` and `gcd(Ei,Hi1) = 1`. Since the residues of F at the roots of Gj are all 0, and the residue of F at a root "a" of Ei is Hi1(a) != 0 , f is the derivative of a rational function if and only if Ei = 1 for each i, which is equivalent to Di | Hi1 for each i.
-- **Marik's Criteria**:
The second approach could be to compute the squarefree factorization D = D1,D2...Dm of the denominator of F, and write `F = Sum(i,1,n) Ai.Di^1`If F is the derivative of a rational function, then D1 | A1, since the residuesof F at the roots of Di would be nonzero otherwise. If D1 | A1, then f is the derivative of a rational function if and only if each Ai/Di^i is the derivative of a rational function for i > 1, and we can use Marik's criterion, which states that A/D^m is the derivative of a rational function for m > 1 if and only if `D | Wronskian(dD/dx, dD^2/dx, .... dD^m-1/dx, A)`

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.


2. **Recognizing Log Derivative**
Inorder to determine whether there exists u in K{x)* such that du/dx = uf ie F is the logarithmic derivative of a rational function, if and only if F can be written as F = A/D where D is squarefree, deg(A) < deg(D), gcd(A, D) = 1,and all the roots of the Rothstein-Trager resultant are integers.
I am mostly done with this section.Have implemented:
* recognize_log_derivative(refer to PR https://github.com/sympy/sympy/pull/2002 for more details)

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)

where delta(t) = D degree of t , lambda(t) = D leading coefficient of 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

Add a custom footer
Add a custom sidebar
Clone this wiki locally