GSoC 2015: Improving series and limits in sympy

[Sartaj Singh]

Series in sympy lacks proper structure. This structure needs to be flexible and general. I have tried to give it a proper structure, on which different series expansions can be built. I have written a draft of the proposal. Please suggest possible changes and improvements.

[Sartaj Singh]

I have also posted the proposal on the wiki https://github.com/sympy/sympy/wiki/GSoC-2015-Application-Sartaj-Singh:-Improving-the-series-package-and-limits-in-SymPy. I would really like to know the views of the community, also what other areas should I touch.

[Sartaj Singh]

As a part of my GSoC project, I would also like to work on computing limits of sequences. This is what I have come up wiith so far.

Implementing this algorithm will allow computing limits of some summations, which is not currently computed by sympy. This will improve the range of admissible functions of which limit can be computed. Algorithm for computing limits of sequences is explained in the paper "Computing Limits of Sequences" by Manuel Kauers.

Applicability Criteria:

This algorithm can be applied if the following conditions are fulfilled

* Applies on expressions of the form pn/qn where pn, qn tends to oo when n tends to oo

* qn should be asymptotically strictly monotonous.

* terms are built from rational functions, indefinite sums and indefinite products over an indeterminate n, called Pi Sigma - expressions.

Algorithm Details:

Difference operator, is defined as

  D(an) = a(n+1) - a(n)

Also, if

limit (n -> oo) pn/qn = 0, then qn is the dominant term

* Check for the applicability criteria's as described in the above section.

* Use the difference operator on the numerator and denominator.

* Find the dominant term of the numerator and the denominator. Drop all other terms.

* Keep on doing recursively, until limit converges to a value.

However I have some questions regarding the implementation:

* Is there any implementation of difference operator presently in Sympy, I did not find any. I might have missed.

* What would be the best possible way for finding the most dominant term. Is there a suitable implementation already implemented in gruntz module?

* One way to implement, is to implement it as a new function and integrate it inside limit. Any other approach?

[Sartaj Singh]

I have updated my proposal, [here](https://github.com/sympy/sympy/wiki/GSoC-2015-Application-Sartaj-Singh:-Improving-the-series-package-and-limits-in-SymPy). Please have a look.

[Ondřej Čertík]

Hi Sartaj,

I looked at the proposal. How will the series be represented
internally? I did some investigation here:

https://groups.google.com/d/msg/sympy/hiRuIHa8ImA/2Y__l-hB-cEJ

What do you think of it? It seems to me the best way to implement the
SeriesData is to use the ring series from sympy. I.e. finish it up to
support all the needed operations and then use it. Let me know, we can
discuss this more.

Ondrej

> --
> 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 post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/89e370d8-30b7-4620-8b61-ae17360fe90b%40googlegroups.com.
>
> For more options, visit https://groups.google.com/d/optout.

[Sartaj Singh]

It looks like ring_series, works only for finite cases, can it be extended for infinite case? SeriesData will just zip two sequences together. It is more general as variables can even be of the form sin(n*x), and not only x. In the main FormalPowerSeries class, I plan to provide an infinite representation of series. 

Ring_series is undoubtedly fast, so it is a plus to use it in my implementation. I have glanced over the code of ring_series, and it may be modeled into the structure I propose, i.e based on sequences. The algorithms in ring_series can be used for manipulating truncated form of the series. 

In summary, I think SeriesData should be left as a higher abstraction, and operations for truncated series can be added in SeriesX or in FormalPowerSeries. Let me know what you think.

Regards

Sartaj Singh

[Ondřej Čertík]

On Mon, Mar 23, 2015 at 1:41 AM, Sartaj Singh <singhs...@gmail.com> wrote:
> It looks like ring_series, works only for finite cases, can it be extended
> for infinite case? SeriesData will just zip two sequences together. It is
> more general as variables can even be of the form sin(n*x), and not only x.
> In the main FormalPowerSeries class, I plan to provide an infinite
> representation of series.

I think the ring series can only be used for n terms, i.e. if you have
some expression, like sin(x)*cos(x), then you first expand sin(x) and
cos(x) into n-terms, and then you multiply them out, and cut the
result appropriately (at n-terms in this case).

But you can use any "n". How do you store infinite number of terms in
your approach?

> Ring_series is undoubtedly fast, so it is a plus to use it in my
> implementation. I have glanced over the code of ring_series, and it may be
> modeled into the structure I propose, i.e based on sequences. The algorithms
> in ring_series can be used for manipulating truncated form of the series.
>
> In summary, I think SeriesData should be left as a higher abstraction, and
> operations for truncated series can be added in SeriesX or in
> FormalPowerSeries. Let me know what you think.

That would work.

Ondrej

[Sartaj Singh]

I think the ring series can only be used for n terms, i.e. if you have
some expression, like sin(x)*cos(x), then you first expand sin(x) and
cos(x) into n-terms, and then you multiply them out, and cut the
result appropriately (at n-terms in this case).

But you can use any "n". How do you store infinite number of terms in
your approach?

FormalPowerSeries class, will compute the explicit formula for finding the coefficients. This formula can be plugged in sequences, which will generate coefficients lazily. Computed coefficients will be stored in a sparse representation (python dictionary), for retrieval at a later stage. The main benefit of this is that now users will be able to play around with infinite representation of Formal Power Series  (addition, subtraction, etc) without explicitly computing the coefficients. Only computing when required. Much of this is inspired from lazy evaluation in Haskell.

 

Sympy only supports truncated representation of series for now. My approach will allow infinite representation as well. Should series by default be truncated? (this allows good use of ring_series) or should their be separate representations for infinite and truncated representation?

[Sartaj Singh]

Another way can be to have truncated series by default and use ring_series for operations. User can access infinite representation as a property if available.

Regards

Sartaj Singh

[Aaron Meurer]

I think you guys are perhaps talking past each other. To Ondrej,
"series" means "series approximation", whereas to "Sartaj" it menas
"formal power series". Both are mathematically related, but from a CAS
point of view they are quite different.

Formal power series is something that would be nice for SymPy to have,
but my understanding is that the summation algorithms will need to
improve a lot for you to be able to compute anything nontrivial (like
Cauchy products).

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 post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.

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

[Sartaj Singh]

On Tuesday, 24 March 2015 22:25:04 UTC+5:30, Aaron Meurer wrote:

I think you guys are perhaps talking past each other. To Ondrej,
"series" means "series approximation", whereas to "Sartaj" it menas
"formal power series". Both are mathematically related, but from a CAS
point of view they are quite different.

 

Oh, I see. I am inclined towards infinite representation of Formal Power Series. But it is easy to represent it in truncated form.

  

Formal power series is something that would be nice for SymPy to have,
but my understanding is that the summation algorithms will need to
improve a lot for you to be able to compute anything nontrivial (like
Cauchy products).

 

Yes, you are correct summation algorithm need to be improved, some formulas are quite involved. But it will be nice to use ring_series for various operations for truncated series. When summations algorithm improve, non-trivial cases can be implemented for infinite series.

Sartaj Singh

[Shivam Vats]

But it will be nice to use ring_series for various operations for truncated series.

ring_series has very fast implementations of the series expansion of elementary 

functions (currently it has log and exp only). Consider this:

 

In [18]: %timeit s = exp(x).series(x, 0, 100)

1 loops, best of 3: 7.01 s per loop

In [20]: %timeit t = rs_exp(y, y, 100)

100 loops, best of 3: 4.29 ms per loop