On Sat, Nov 23, 2013 at 11:23 PM, Ondřej Čertík <[email protected]> wrote: > On Sat, Nov 23, 2013 at 10:53 AM, Aaron Meurer <[email protected]> wrote: >>> On Nov 22, 2013, at 11:03 AM, "Ondřej Čertík" <[email protected]> >>> wrote: >>> >>> Hi, >>> >>> Currently the series are represented as a regular symbolic expression, >>> with the Order() instance added to it. >>> >>> I think we should rather represent series as a Series class, roughly >>> equivalent to SeriesData in Mathematica: >>> >>> http://reference.wolfram.com/mathematica/ref/SeriesData.html >>> >>> The Series class would interact with SymPy similar to how Poly works in >>> SymPy. >>> The Series would represent a series expansion in one variable (I don't >>> have opinions about multiple variables yet), so it would remember the >>> terms in some suitable format (see below, just like for Polys, there >>> are more options on the internal representation) and the order of the >>> series. Then, when you print it, it will print it just like we >>> currently do, with the "O(x^2)" term, though that's just how it is >>> printed. >> >> And also remember the original expression! > > If it is available (i.e. when you sum or multiply two Series, there > is no original expression).
Wouldn't it just be the product of the original expressions? Keeping track as much as possible is useful so that you can have some kind of extend() method that just extends the series with more terms (efficiently). > >> >>> >>> The Series would have methods like differentiate, invert, etc. >>> >>> If you look at how GiNaC does it: >>> >>> https://github.com/certik/ginac/blob/master/ginac/pseries.h >>> https://github.com/certik/ginac/blob/master/ginac/pseries.cpp >>> >>> They have a class pseries for it. Their representation is a list of >>> (coefficient, power) pairs (plus series variable and expansion point): >>> >>> https://github.com/certik/ginac/blob/master/ginac/pseries.h#L112 >>> >>> In Mathematica, they only have a list of coefficients for all powers >>> from nmin/den to nmax/den (so some coefficients could be zero), plus >>> series variable and expansion point. In Ginac, when they convert the >>> series to an expression: >>> >>> https://github.com/certik/ginac/blob/master/ginac/pseries.cpp#L593 >>> >>> they simply attach the Order instance. >>> >>> Conclusion: Mathematica is using dense representation of series, while >>> GiNaC is using a sparse representation (instead of a list, one can >>> also use a dictionary). I currently don't know which one is better, >>> maybe we should have several implementations, just like Polys. >> >> I don't see the point of sparse, since most series are dense. But see >> what I wrote below. > > While most series are probably dense, e.g. even this one is dense: > > In [1]: (sin(x)**10).series(x, 0, 20) > x**10 - 5*x**12/3 + 4*x**14/3 - 43*x**16/63 + 713*x**18/2835 + O(x**20) > > You can easily construct series that are sparse: > > In [2]: (sin(x**15)).series(x, 0, 100) > x**15 - x**45/6 + x**75/120 + O(x**100) > > So I can definitely see that sparse representation will be faster for > some examples. > > Ondrej I would highly recommend looking at the work Mario did. It's going to be more efficient than any representation that you come up with in just a few minutes, and plus he already wrote a bunch of algorithms around it. The work was https://github.com/sympy/sympy/pull/609, but I have no idea how much of that has been forward ported to ring() and friends. It also looks like some more has been ported at https://github.com/sympy/sympy/pull/2630. I guess Mario will need to comment on the status of it all. Aaron Meurer > >> >>> >>> >>> >>> Open ideas: >>> >>> * I don't like that Order requires special handling in Add: >>> >>> https://github.com/sympy/sympy/blob/master/sympy/core/add.py#L237 >>> >>> So maybe we can just append Order to an expression in Add, but the >>> simplification will be done by the Series class, i.e. no special >>> handling in Add. So there will be a method Series.to_expr(), that >>> would return an Add instance, with Order term appended. Unfortunately >>> if you want to do some stuff like O(x)+O(x^2), then it wouldn't work >>> if O(x) is just an Order. However, one idea could be that if we >>> completely remove Order, and only have Series, then O(x) would simply >>> be an instance of Series. And then just like Polys work, O(x)+O(x^2) >>> would by dispatched to Series, that knows how to simplify it. >>> So Add internally doesn't have to handle simplification of this, only >>> "holding" the terms. >>> >>> * I am thinking how to implement this in CSymPy as well. Thinking >>> about it helps with the design, because in CSymPy, it needs to be as >>> fast as possible. So handling of Order in Add is a nono. In general, >>> the best way is to always have a special algorithm+efficient >>> representation for the given thing. So Add should only handle the >>> usual x+x or x*x thing. Series handling should be done by a special >>> class Series, that knows everything about series expansion and can use >>> efficient representation (both the dense and sparse representation >>> above is more efficient than just the general expression with Order >>> term appended, for things like O(x)+O(x^2) or multiplication or >>> inversion of series). At the same time, what's best for CSymPy might >>> not necessarily be the best for SymPy. But so far it seems to me that >>> we always want to have the best algorithm+datastructures in SymPy, so >>> that it's fast, algorithmically. C++ then only provides a constant >>> speedup, as it doesn't have the overhead of Python. >>> >>> * See also this: >>> >>> https://github.com/sympy/sympy/wiki/UD-Under-Development#series >> >> Also take a look at Mario's work (I think it may be buried in some >> pull request). His implementation will probably be the fastest. >> >> Aaron Meurer >> >> >>> >>> 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 [email protected]. >>> To post to this group, send email to [email protected]. >>> Visit this group at http://groups.google.com/group/sympy. >>> For more options, visit https://groups.google.com/groups/opt_out. >> >> -- >> 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 [email protected]. >> To post to this group, send email to [email protected]. >> Visit this group at http://groups.google.com/group/sympy. >> For more options, visit https://groups.google.com/groups/opt_out. > > -- > 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 [email protected]. > To post to this group, send email to [email protected]. > Visit this group at http://groups.google.com/group/sympy. > For more options, visit https://groups.google.com/groups/opt_out. -- 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 [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out.
