GSoC 2020 Introduction (Thoughts on implementing summation algorithms)

[Neeraj Adhikari]

Hello SymPy Developers,

I am interested in applying to GSoC 2020 so here's my introduction.

I'm a grad student at the University of Rhode Island, currently in my second semester pursuing a Master's Degree in Computer Science. I have strong interests in mathematics in general and specifically the intersection of mathematics and computer science. I have been programming in python on and off since about 2015, when I worked on my undergraduate AI project (a basic chat bot). More recently I used python for a computer vision project in my previous job. The project involved extracting structured information from images of identity cards.

Maple is the CAS I'm most familiar with as I'm using it for course I'm taking. I had heard of Sage before but didn't know that SymPy was its backend for symbolic computation. For GSoC 2020, I want to work on summation algorithms. With SymPy only implementing Gosper's algorithm now, there are a lot of expression classes whose summations cannot be computed. Before the summer, I will be implementing an algorithm that uses generating functions (link to paper) to sum hybrid functions as a project for the course. This algorithm can find sums containing special functions like the harmonic numbers and fibonacci numbers, which SymPy is mostly unable to do now. (For example, summation(k*harmonic(k), (k,1,n)) does not produce a closed form). My implementation for the course will be in the Maple programming language, and my first task would be porting that to SymPy. Once that is done, I want to move on to implementing Karr's algorithm, first for the indefinite case and then the definite case. I think implementing an algorithm I'm already familiar with first might be better than to dive headfirst into the more complex Karr's algorithm. What are your thoughts on this?

Another relevant piece of information: my major professor (Dr. Ed Lamagna) is a computer algebra researcher and has contributed to the implementation of some algorithms in Maple. I will be able to ask him for advice in case I'm stuck on something.

Thanks,
Neeraj

[Oscar Benjamin]

Hi Neeraj,

That all sounds excellent. I don't know the algorithms you are
referring to or the summation code that well myself but I know that it
needs some love!

A GSOC proposal is always more enticing if it demonstrates
understanding of the existing codebase and known problems. It is
probably worth taking a look at the open issues and PRs that have the
concrete label:
https://github.com/sympy/sympy/issues?q=is%3Aopen+is%3Aissue+label%3Aconcrete
https://github.com/sympy/sympy/pulls?q=is%3Aopen+is%3Apr+label%3Aconcrete

Can you see any examples there that could be calculated with the
algorithms you mentioned?

One thing that needs sorting out is a fully precise definition of what
a Sum actually represents. At the moment we have

In [24]: Sum(1, (x, 1, S(1)/2))
Out[24]:
1/2
___
╲
╲
╱ 1
╱
‾‾‾
x = 1

In [25]: Sum(1, (x, 1, S(1)/2)).doit()
Out[25]: 1/2

To me that's gibberish but the question is how non-integer limits
should be interpreted (or whether they should be allowed).

We also have things like this:

In [31]: Sum(1, (x, y, z)).doit()
Out[31]: -y + z + 1

In [32]: Sum(1, (x, y, z)).doit().subs(z, -1).subs(y, 1)
Out[32]: -1

I think that the current summation code is not very mature so be
prepared to find that various surrounding bits need improvement while
implementing the algorithms.


Oscar

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/e51d9e24-149c-45b7-a10d-a42b881f8cf0%40googlegroups.com.

[Aaron Meurer]

The convention used is actually related to the Karr algorithm, in that
it is based on the conventions defined in his paper
https://docs.sympy.org/latest/modules/concrete.html#sympy.concrete.summations.Sum.
It relates to the way so-called indefinite summations work, which are
an important part of the algorithm.

Regarding the project, I would warn that the Karr algorithm is quite
complicated, so it would be good to try to split it into workable
pieces, with the assumption that only some of the first pieces may be
completed over the summer.

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAHVvXxQkqt8ZJg-OSQUyioWM_YiiQo75jb23q3o0-G92UAYyCw%40mail.gmail.com.

[Oscar Benjamin]

On Wed, 11 Mar 2020 at 16:58, Aaron Meurer <asme...@gmail.com> wrote:
>
> The convention used is actually related to the Karr algorithm, in that
> it is based on the conventions defined in his paper
> https://docs.sympy.org/latest/modules/concrete.html#sympy.concrete.summations.Sum.
> It relates to the way so-called indefinite summations work, which are
> an important part of the algorithm.

That might be what it says in the docstring but Sum clearly does not
actually use that convention:

In [6]: Sum(f(n), (n, 1, 4)).doit()
Out[6]: f(1) + f(2) + f(3) + f(4)

[Aaron Meurer]

Yes, I just looked closer and what is written there is quite
confusing. The purpose of the convention is to define what happens
when the upper limit is less than the lower limit. I believe it also
defines what happens when the limits are nonintegral, but I could be
misremembering that. The docstring is correct. It talks about the
notation in the Karr paper, which is non-inclusive, and it tries to
talk about how that relates to the normal summation notation, which is
inclusive (and is what SymPy uses). The section needs to be improved.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAHVvXxShNbxx-N5UGd3OXRAXaeLLRgNtGc6syagpPKw6ZXuwOg%40mail.gmail.com.

[Neeraj Adhikari]

I couldn't find any examples in open issues which require the generating function algorithm to solve. I will keep looking at the issues and the codebase to better understand them.

As for the Karr Algorithm, thank you for the suggestion! I will split its implementation to smaller pieces and propose working on the first few ones in my proposal.

> > To unsubscribe from this group and stop receiving emails from it, send an email to sy...@googlegroups.com.

> > To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/e51d9e24-149c-45b7-a10d-a42b881f8cf0%40googlegroups.com.
>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to sy...@googlegroups.com.

[Gagandeep Singh (B17CS021)]

The PR, https://github.com/sympy/sympy/pull/14701 might be of interest. It implements an algorithm for computing hypergeometric sums.

To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/262581c6-de40-41c1-b3e5-659363623a1e%40googlegroups.com.

--

With regards,

Gagandeep Singh

Github - https://github.com/czgdp1807/

Linkedin - https://www.linkedin.com/in/czgdp1807/