Discussion regarding the series expansion project

[Avichal Dayal]

There are only two weeks before student application portal opens
and I would like to discuss my ideas regarding "Series expansion" project.

Here is what SymPy currently does:-
series:-
1) General expansion with O term appended
2) No separate functions for taylor, laurent, asymptotic etc.
3) Cannot provide a generating function or an infinite series representation
4) Bugs when expansion point is other than zero

For 3) we need to implement Formal Power Series
Formal Power Series:
    Other CAS like Maple, Mathematica have this functionality and we must also have it.
    This has two parts:
    1) Give a formula or sequence and get the infinite series
    2) Give a function and get the infinite series
    Once we get the infinite series, we can do various operations on it.
    
    Main points:
    1) Representation of infinite sum. Is there a way to represent summation yet in SymPy?
    2) Implement algorithm that can create a generating function given an expression.
        This paper gives such an algorithm: http://www.mathematik.uni-kassel.de/~koepf/Publikationen/SC-93-31.pdf
        It uses recurrence relations and differential equations to do so. I'm currently going through it
        and understanding it.
        
Asymptotic Expansion:
    Many special and elementary functions do not have it implemented. I plan to do
    it for all whose expansion is possible.
    
    In general also SymPy does not do it properly.
    For e.g.:-
        series(sin(1/x+exp(-x))-sin(1/x), x, oo, 2) currently gives O(1/x**2)
    It can be better expanded as:-
        1/exp(x) - 1/(2*exp(x)*x**2) + O(1/(exp(x)*x**4))
        
    The following paper gives an algorithm to find such an asymptotic expansion:
        A new algorithm for computing asymptotic series by "Dominik Gruntz"
   
    Main points:
    1) When to do an asymptotic expansion?
       Currently, series just replaces x->1/x and oo->0 and does normal
        series expansion on the project.

Order Term arithmetic:
    This PR by @skirpichev currently deals with it: https://github.com/sympy/sympy/pull/2427
    I'll be more than happy to work on it and extend it.
    
Please reply to give your opinion. Thank You!

[Aaron Meurer]

There was some paper about computing limits with oscillating
functions. Maybe you can find the reference if you search the mailing
list archives (or probably Raoul will remember it).

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/af766c64-f73e-46aa-8b00-393fb9ca82ac%40googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[Sergey Kirpichev]

On Wednesday, February 26, 2014 6:03:22 AM UTC+4, Aaron Meurer wrote:

There was some paper about computing limits with oscillating
functions. Maybe you can find the reference if you search the mailing
list archives (or probably Raoul will remember it).

Probably, it's a good idea to search first in google code issues, tagged with "Series".

[Avichal Dayal]

Well, I'll search the archives and the issue page to look for the paper.

Besides that, I am more interested in implementing formal power series for SymPy.
Does it seem like something the SymPy community would want? Personally I'm very
excited to implement it and I feel we must have it.

Series of some function apart from the current result should also return an infinite series
in terms of a generating function. It would be great if we have it.

[Alexey U. Gudchenko]

If this paper is significant for something then it is better to add it
to the wiki page

Who is paper's author? Joris van der Hoeven [1] or Gruntz [2]?

Those links are fomded from mailists

[1] http://www.texmacs.org/joris/phd/phd-abs.html
[2] http://www.cybertester.com/data/gruntz.pdf


Or from the https://github.com/sympy/sympy/wiki/GSoC-2014-Ideas

"Formal Power Series" by Dominik Gruntz and Wolfram Koepf
"A New Algorithm Computing for Asymptotic Series" by Dominik Gruntz
"Computing limits of Sequences" by Manuel Kauers
"Symbolic Asymptotics: Functions of Two Variables, Implicit Functions"
by Bruno Savly and John Shackell
"Symbolic Asymptotics: Multiseries of Inverse Functions" by Bruno Savly
and John Shackell


--
Alexey Gudchenko

[someone]

Hi,

> There was some paper about computing limits with oscillating
> functions. Maybe you can find the reference if you search the mailing
> list archives (or probably Raoul will remember it).

Let me search for it. I think I know which one you refer to.
However there was little concrete information in there:

"Asymptotic estimation of oscillating functions using an interval calculus"
by John Shakell

"On the computation of limsups"
by Joris van der Hoeven

Probably the best reference to read in case we really want to go beyond what
Gruntz can do is the thesis "Automated Asymptotics" of Joris van der Hoeven.
It is very advanced on the mathematics side though.

Let me know if you need more information.

[Avichal Dayal]

Thank you for the references.

Anyways what about this?

I am more interested in implementing formal power series for SymPy.
Does it seem like something the SymPy community would want?

I am asking this as I don't want to work on something that the community doesn't
want.

I am planning to work on formal power series, asymptotic expansion and order
term arithmetic. Will that be the right amount of work for the summer?
 

[Sergey Kirpichev]

On Thursday, February 27, 2014 9:14:30 AM UTC+4, Avichal Dayal wrote:

I am planning to work on formal power series, asymptotic expansion and order

term arithmetic. Will that be the right amount of work for the summer?

Yes, that's very *big* amount of work.  btw, I think now (see pr #2630) we have
some functions in polys module for first task.

[Avichal Dayal]

Yes, that's very *big* amount of work.

You mean enough for the summer
or too much for the summer?

Since this project involves several sub-projects as per your suggestion
I should focus on:
1) formal power series
2) asymptotic expansion
3) some functions in polys module
right?

[Sergey Kirpichev]

On Friday, February 28, 2014 12:01:10 AM UTC+4, Avichal Dayal wrote:

Yes, that's very *big* amount of work.

You mean enough for the summer
or too much for the summer?

It depends on what is exactly you are planning to do.

[Avichal Dayal]

Formal power series requires a sequence class.
However it is already implemented here: https://github.com/goodok/sympy/tree/sequences/sympy/sequences
It is not merged yet.

Can I use the same for my project or should I re-implement it?

[Ondřej Čertík]

It's open source, of course you can use it. You should use it, if it's good.

Ondrej

[Aaron S. Meurer]

All I remember was that there was an introduction in another language (French possibly), and it was on a mailing list discussion with Tom. I can probably find it with a little searching when I get to my computer.

Aaron Meurer

Sent from my iPhone.

> On Feb 26, 2014, at 6:51 PM, someone <some...@bluewin.ch> wrote:
>
> Hi,

>
>> There was some paper about computing limits with oscillating
>> functions. Maybe you can find the reference if you search the mailing
>> list archives (or probably Raoul will remember it).
>

[Alexey U. Gudchenko]

On 05.03.2014 22:17, Avichal Dayal wrote:
> Formal power series requires a sequence class.
> However it is already implemented here:
> https://github.com/goodok/sympy/tree/sequences/sympy/sequences
> It is not merged yet.

No, it is only the prototype (model), experiment with some restrictions.

It not well embeded in the current sympy state (and have some structural
reasons to be impossible).

As I understand, the current embeded multivariant versions of series
(not pure formal power series, but rather series expansion) is based on
the polys series_rings and developed by Pernici in

https://github.com/sympy/sympy/blob/master/sympy/polys/ring_series.py

>
> Can I use the same for my project or should I re-implement it?
>

Sure, but I must introduce about some problems of this direction.


1. It is only one variable formal power series.
2. It is combined with helper Sequences object (which is thing itself)

And thechnically:

3. As it was created long time ago the multidispatche constructions (and
other things) may be depricated.

4. It is not well computable with the core/Mul.flatten and
core/Add.flatten methods (as they not well destined).

5. __str__ representation is only for view to be convinient. __repr__
only for the object representation.



--
Alexey Gudchenko

[Avichal Dayal]

It would be great if you could look at my proposal (just an initial draft) and give suggestions:-
https://github.com/sympy/sympy/wiki/GSoC-2014-Application-Avichal-Dayal-Series-Expansion

Thank You!

[Aaron Meurer]

Yeah, I searched the archives, and those were they. In particular, the
last one, http://www.texmacs.org/joris/phd/phd-abs.html, seemed to
have some ideas. There were also some interesting ideas on this
thread https://groups.google.com/d/msg/sympy/h3aVz3y3n7g/JtqyPMakotMJ.

HTH

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/530e8c0b.49d50e0a.3c34.5aabSMTPIN_ADDED_BROKEN%40gmr-mx.google.com.

[deepak goel]

actually that paper involves making use of transseries. but before that we can first extend what we have in gruntz.py. actually Sympy lacks effecient implementation of gruntz thesis
By integrating hardy fields(something thing that sympy basically exp-log functions) with nested expansions and star products, we can effeciently deal with not only exp-log functions but also liovillian func, inverse functions and implicit functions as explained in symbolic asymptotics book by shackell

[Avichal Dayal]

The paper you mention works for functions containing only bounded functions like:-
(sin(x**2) - sin(x))/(3 + cos(E*x**2))

And I think that's what we need. Heuristics handle cases like sin(x)/x but not when
all are bounded. This can be a useful addition.

I've partly understood the algorithm and I plan to add it to my proposal. Can you give some suggestions
regarding my proposal? I plan to do formal power series, asymptotic series and hopefully limits.

Here is the link:-
https://github.com/sympy/sympy/wiki/GSoC-2014-Application-Avichal-Dayal-Series-Expansion

[Alexey U. Gudchenko]

On 12.03.2014 00:12, Avichal Dayal wrote:
> The paper you mention works for functions containing only bounded
> functions like:- (sin(x**2) - sin(x))/(3 + cos(E*x**2))
>
> And I think that's what we need. Heuristics handle cases like
> sin(x)/x but not when all are bounded. This can be a useful
> addition.
>
> I've partly understood the algorithm and I plan to add it to my
> proposal. Can you give some suggestions regarding my proposal? I plan
> to do formal power series, asymptotic series and hopefully limits.
>

About strategic (for all)

> Here is the link:-
> https://github.com/sympy/sympy/wiki/GSoC-2014-Application-Avichal-Dayal-Series-Expansion
>

> Formal Power Series:
>
> Other CAS are capable of returning an infinite series in terms of a
> generating function or a sequence. I feel we should have this.
> Currently series() returns something like 1 + x + x**2/2 + O(x**3)
> while Mathematica and others are also capable of returning something
> like summation(x**n/factorial(n), (n, 0, oo)).
>

1. Is it possible strategically to combine this model with multy
variable cases development in [1] with usage of polys (and some special
fast polynomials bases)? In this case there is no special structures as
Sequences, Generating functions and so on.

2. What is more "symbolical": description of series: via some structure,
or only as the coeffitients (symbolical thou) of some restricted number
of terms? What is common for them?

> Asymptotic series:
>
> Most of the routines are implemented in gruntz.py. However still work
> is to be done to implement it. Series is extensively used by gruntz
> and asymptotic expansion is not implemented in SymPy. This would
> improve gruntz greatly.

3. Is it transseries [4]?

4. If it is transseries, what is better (for what aims) to implement
firstly: Formal Transseries (without consideration of limits), or series
expansion ( restricted number of terms).

5. Is it possible or impossible to combine transseries with [1] or with
lazy Series structure [2]?


And may be outside the context of your Application

6. Is it possible to implement multi variable cases so, to keep in mind
abstract FPS, functions and Sequences (or, obviously, something instead
of abstract Sequences but rather tensors) as in [3]?


Links:

[0]
https://github.com/sympy/sympy/wiki/GSoC-2014-Application-Avichal-Dayal-Series-Expansion

[1] https://github.com/sympy/sympy/blob/master/sympy/polys/ring_series.py

[2]
https://github.com/sympy/sympy/wiki/UD-Sequences-and-formal-power-series-prototype

[3] http://www.goodok.ru/sympy/series/series-sympy-example.pdf

[4] http://arxiv.org/abs/0801.4877 "Transseries for beginners" G. A. Edgar


--
Alexey Gudchenko

[Sergey Kirpichev]

Hello,

> Formal Power Series:

What about Lambert series?

> Currently series() returns something like 1 + x + x**2/2 + O(x**3) while
> Mathematica and others are also capable of returning something like
> summation(x**n/factorial(n), (n, 0, oo)).

I'm little surpised. Can you provide an example of this from
the Mathematica?

> Basic class structure: <--FormalSeries-->

Very unclear. That's all to say.

> Representation of infinite series: ... I'm planning to represent it
> using ordered term of (coeff, exponent) knows as “lazy evaluation” in
> the literature.

Probably, you should think about multivariable series too.

> We will need a sequence object to represent sequences. This is already
> implemented here:
> https://github.com/goodok/sympy/tree/sequences/sympy/sequences. However
> the code is old and does not play nice with current SymPy structure. I
> plan to re-implement it based on a similar model.

I don't think it's a good idea. We should have instead a basic
container type (cf. tuple or list) for infinite sequence (take look on
Stream class in the "fn" python package). Then, we can
wrap it like Tuple or Dict.

[Alexey U. Gudchenko]

On 14.03.2014 14:24, Sergey Kirpichev wrote:
> Hello,
>
> On Fri, Mar 7, 2014 at 3:29 AM, Avichal Dayal <avicha...@gmail.com>wrote:
>> It would be great if you could look at my proposal (just an initial draft)
>> and give suggestions:-
>> https://github.com/sympy/sympy/wiki/GSoC-2014-Application-Avichal-Dayal-Series-Expansion
>
>> Formal Power Series:
>
> What about Lambert series?

Do you meant Laurent series?


--
Alexey Gudchenko

[Sergey Kirpichev]

On Friday, March 14, 2014 6:24:15 PM UTC+4, pr...@goodok.ru wrote:

Do you meant Laurent series?

Yep, sorry

[Avichal Dayal]

I'm little surpised.  Can you provide an example of this 
from the Mathematica?

I don't have the software. But I have seen examples in 

the references.

Wolfram gives both the truncated series with the order 

term and using generating functions as shown below:

In[1] := FormalSeries(exp(x), x)
Out[1] := Summation(x**k/k!, (k, 0, oo))

In[2] := FormalSeries(cos(x), x)
Out[2] := Summation((-1)**k * x**(2*k) / (2*k)!, (k, 0, oo))

I don't think it's a good idea.  We should have instead a 
basic container type (cf. tuple or list) for infinite sequence 

Thanks for the suggestion. We will already have the 

formula produced by the algorithm or given by the user. 

Then we can use stream to calculate and store the infinte 

sequence. But is it encouraged to use "fn" library?

Is it possible strategically to combine this model with 
multy 
variable cases development in [1] with usage of polys 
(and some special 
fast polynomials bases)? In this case there is no special 
structures as 
Sequences, Generating functions and so on.

I'll drop the idea of sequence and use Stream class in 

"fn" as @skirpichev pointed out.

Other than that I only need to store the formula used to 

generate the sequence. 

I can store that as an expression or as a tuple of (coeff and exponent)?

I'll improve the FormalSeries class description and try to add multivariable case soon. Any other suggestions?

[Alexey U. Gudchenko]

On 16.03.2014 17:52, Avichal Dayal wrote:
>
>>
>> I'm little surpised. Can you provide an example of this
>> from the Mathematica?
>
> I don't have the software. But I have seen examples in
> the references.
> Wolfram gives both the truncated series with the order
> term and using generating functions as shown below:
> In[1] := FormalSeries(exp(x), x)
> Out[1] := Summation(x**k/k!, (k, 0, oo))
>
> In[2] := FormalSeries(cos(x), x)
> Out[2] := Summation((-1)**k * x**(2*k) / (2*k)!, (k, 0, oo))
>

The nearest similar thing in the last version of Mathematica 9.0 is
SeriesCoefficient:

https://reference.wolfram.com/mathematica/ref/SeriesCoefficient.html

And the old package of Wolfram Koepf (not Steven) for Mathematica 2.0

http://arxiv.org/abs/math/9404219

>
> I don't think it's a good idea. We should have instead a
>> basic container type (cf. tuple or list) for infinite sequence
>
> Thanks for the suggestion. We will already have the
> formula produced by the algorithm or given by the user.
> Then we can use stream to calculate and store the infinte
> sequence. But is it encouraged to use "fn" library?
>
> Is it possible strategically to combine this model with
>> multy
>> variable cases development in [1] with usage of polys
>> (and some special
>> fast polynomials bases)? In this case there is no special
>> structures as
>> Sequences, Generating functions and so on.
>
> I'll drop the idea of sequence and use Stream class in
> "fn" as @skirpichev pointed out.

In this case take into account
http://www.sagemath.org/doc/reference/sage/combinat/species/series.html

Can Stream (or wrapper) be used for a few variables?

> Other than that I only need to store the formula used to
> generate the sequence.
> I can store that as an expression or as a tuple of (coeff and exponent)?

It depends of use-cases.
For example [1] used some polynomial bases.

And not principal before undefined strategic.

Firstly we must divergent tasks:

a) Formal Power Series (it is one thing: generating functions, possibly
infinity number of coefficients, which defien FPS)

b) Series Expansion, then Transeries Expansion.
Used for for the expansion, limits

And extend all/one of them for multivariables.
And, possibly, combine (as FindGenerationFunctions (that is formula)
from a few terms, that is the reverse task of expansions)

In my opinion we must concentrate only for the one tasks a) or b), but
taking into account both.

Links:

[0]
https://github.com/sympy/sympy/wiki/GSoC-2014-Application-Avichal-Dayal-Series-Expansion

[1] https://github.com/sympy/sympy/blob/master/sympy/polys/ring_series.py

[2]
https://github.com/sympy/sympy/wiki/UD-Sequences-and-formal-power-series-prototype

[3] http://www.goodok.ru/sympy/series/series-sympy-example.pdf

[4] http://arxiv.org/abs/0801.4877 "Transseries for beginners" G. A. Edgar

[5] http://www.sagemath.org/doc/reference/sage/combinat/species/series.html

[6] http://arxiv.org/abs/math/9404219

--
Alexey Gudchenko

[Sergey B Kirpichev]

On Sun, Mar 16, 2014 at 06:52:14AM -0700, Avichal Dayal wrote:
> But is it encouraged to use "fn" library?

No.

[Aaron Meurer]

Going from functions to summations would be useful, though I'm not
sure if such a thing would be required or even useful for the series
module. The last time we discussed it, the conclusion was that we need
stronger summation algorithms, so that we have some hope of
simplifying the product or composition or inversion formulas.

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/20140316171114.GA7115%40darkstar.order.hcn-strela.ru.
> For more options, visit https://groups.google.com/d/optout.

[Avichal Dayal]

I think the best way to store the generating function is as wikipedia describes it: http://en.wikipedia.org/wiki/Formal_power_series#Power_series_in_several_variables
Similar to lpoly1 PR by pernici it will have a structure.
It will be of the form c*X**a where X**a is a monomial in serveral variables and c defined on an arbitrary ring.

I also realize that many complicated operations on FPS like composition, convolution won't result in simplified summation representation because of weaker summation algorithms. That's a part of my project but I think implementing them nonetheless should be a good idea.

Also I added more examples and explanations in unclear areas.
Thank you for your comments

[deepak goel]

actually i partly agree with aaron. formal power series plays a good role in mathematical physics but now before that sympy needs something for product ,inversion , sum and exp-log operations which structures like nested expansion and multiseries provide. thats why i am solely focused on these things in my proposal. i think that with fps can be quite fruitful for sympy. i have submitted same at melange. i think both things will go together