GSoC 2012 Application Saurabh Jha: implementing algorithm to find the limits of series - sympy/sympy GitHub Wiki

FINDING LIMITS OF SERIES

Short description: Sympy is a computer algebra system implemented in Python. Currently, Sympy is using Gruntz algorithm for series expansion, which is not suitable for certain kinds of expressions. My proposal is to implement Manuel Kauers' algorithm described in the abstract and poster "Computing Limits of Sequences".

NAME: Saurabh jha

UNIVERSITY/CURRENT ENROLLMENT: Guru Nanak Dev University, Gurdaspur, India

MAJOR: Computer Science and Engineering

CURRENT STANDINGS: 2nd year student

ABSTRACT:

Sympy is a computer algebra system implemented in Python. Currently, Sympy is using Gruntz algorithm for series expansion, which is not suitable for certain kinds of expressions. My proposal is to implement Manuel Kauers' algorithm described in the abstract and poster "Computing Limits of Sequences".

SYNOPSIS:

Finding limits of associated series can be comparatively easy, if the limit of the original function is hard to find. Furthermore, we need to find the limits of series as a basis for new algorithms like finding limits of Riemann sums for the calculation of definite integrals. The Gruntz Algorithm used presently to find limits of series does a very good job in finding limits of series, but this algorithm will not work in the following cases: For Discrete Functions For Nested Series Frequently, these problems arise in practical applications in science and engineering. Sympy should supply the users tools to solve these kind of problems too. To solve these kind of problems, I propose to implement Kauers' algorithm described in the paper and the poster “Computing Limits of Sequences” as my project for Google Summer of Code 2012.

HOW IT WILL BE DONE:

The main algorithm is described as follows:

Test if he expression is admissible (if the scopes of all occurring asymptotically positive) 
Apply the L' Hospital rule 
Find the dominant term of both numerator and denominator                  if the limit is finite: 

          exit
      else
          goto step2  

The implementation of this algorithm in turn needs the following  functions

A predicate to check if the expression is admissible This will be done by checking if the function is greater than 0 for n> some fixed number
A function to implement l' hospital's rule. This function in turn needs another function difference operator Δ

        Δ operator is defined as the  difference between two consecutive terms of a sequence. When this function is applied to a sequence, it will take it's two general consecutive terms and find their difference. For example-

a(n)=3n^2 + 2n + 3

This operator will calculate

a(n+1)= 3(n+1)^2 + 2(n+1) + 3

and subtract it from the previous expression.

I also propose to implement the behavior of Δ as follows-

Δ(a+b)= Δa + Δb

Δ(a-b)= Δa - Δb

Δ(ab)= aΔb+bΔa

Δ(a/b)= (bΔa-aΔb)/b^2

After it's implementation, l' hospital's rule will be implemented as

lim n-> ∞ [a(n) / b(n)] = lim n-> ∞ [Δa(n) / Δb(n)]

 A function to find the dominant term of an expression An algorithm to implement this function is described below---



Take the first two numbers, divide them, and find it's behavior as lim n-> ∞
if it approaches ∞ 

         take the first and third term and goto step1 of this algorithm
        
      elif it approaches 0
         
         take the second and third term and goto step2 of this algorithms

      else

         goto step2 of the main algorithm

SUCCESS CRITERIA:

The Kauer's abstract gives some examples under the heading “Some Examples”, which can be used to test if the algorithm is correctly working or not.

TIMELINE:

BEFORE 21st OF MAY

Familiarizing myself completely with the codebase, Reading documentation in more depth, getting input and feedback from sympy community, attaining more mathematical background, if required.

FIRST THREE WEEKS

Implementing a predicate to check if the expression is admissible
         
Implementing Δ operator along with all it's properties

NEXT TWO WEEKS -

Implementing l'hospital's rule

NEXT TWO WEEKS -

Implementing the function to find the dominant term of the expression

NEXT THREE WEEKS-

Implementing the main algorithm using the functions defined above

FINAL TWO WEEKS--

Checking inconsistencies, scope of improvement testing with examples. writing documentation

ABOUT ME:

I am studying Computer Science and Engineering at Guru Nanak Dev University, Gurdaspur, India. I am in my second year. I am very interested in mathematics. In my high school, I had studied calculus for single variable. In college, I studied multivariable calculus as well as infinite series. I have read Manuel Kauers' abstract and poster “Computing limits of series” and completely understood the main points of the paper. I have no other commitments besides summer of code this summer, so I can devote myself fully to the work

REFERENCES:

Computing limits of sequences- Manuel Kauers
 On Computing Limits in a Symbolic Manipulation System- Dominik Gruntz