series and expansion.

[Chris Dams]

Hi Richy,

On Wed, 16 Jun 2004, Richard B. Kreckel wrote:

> On Tue, 18 May 2004, Chris Dams wrote:
> > Some time ago I sent a patch to prevent .series() to revert to .expand()
> > internally. This was because in the case that one has
> > polynomial^some_large_integer the expansion will be hopeless. However, I
> > keep running into this kind of problems. To determine the real_ldegree in
> > mul::pseries, still expansion is used with potentially the same problems.
> >
> > I think there are two possible solutions to this problem.
> > (1) Tell your users (me included) that they should not be substituting
> > polynomials into each others when they should have used power series from
> > the start.
> > (2) Create (or ask me to create) a patch that solves this particular case
> > and hope that there will not be ten other instances where .series() is
> > going to crash a program.
> > (3) Forbid any occurance of .expand() in any method or function that may
> > be called from .series(). Create a new method to determine the leading
> > behaviour of any expression. Let .series() use this and let .series() work
> > by calculating power series of subexpressions and combining these into the
> > power series for the entire expression.
> >
> > I am in favour of (3). The only reason not to use (3) would be if someone
> > in this mailing list could come up with an example where (3) clearly is
> > horribly inefficient.
> >
> > What do other people think?
>
> The third suggestion sounds quite attractive.  If I am not mistaken it
> does, however, lead to some circular reasoning.  The question is: how
> would you go ahead implementing a reliable ldegree routine?  Consider a
> deeply nested expression -- maybe a nested unexpanded polynomial is
> enough.  What's the reliable ldegree?  You would recursively descent into
> the expression tree, inspect candidate expressions, collect their
> coefficients and finally you would have to test this coefficient for zero,
> right?  If it is zero, then start over again with the next degree. Let's
> leave the problem of testing for zero aside.  That would have to be dodged
> like we do in other places (pivoting, e.g.).
>
> However, come to think about it, that procedure sounds a lot like the
> process of series expansion itself!

It sounds like series expansion as it is currently implemented. The
difference is that I only want to tell every type of expression how to
series expand itself if its subexpressions are series. The multiple (!)
differentiation and expansion that occurs in basic::series invites
expression explosion. The "deeply nested expression" that you were talking
about is likely going to result in this, by the chain rule, especially if
a few of the levels in the deep nesting are additions with a not too small
amount of terms. Apart from that, I do not think drastic changes are
necesary.

When I am calculating something by hand on the blackboard, where keeping
expressions size in check is even more crital, I will (almost?) always
series expand by series expanding subexpressions.

It is true that determining the leading term potentially needs series
expansion itsself. However, the current ldegree appear to be primarily
designed for use with polynomials.  I think it would be good if it were
supplemented by something that knows how to handle more general
expressions.

> In the end, I suspect one would have to fundamentally rewrite the whole
> series expansion such that it can be used like a stream.

This sounds like an iteresting idea. Moreover, it sounds like an efficient
idea. The orderloops as they currently appear in GiNaC do not look
efficient. They look like potentially duplicating, triplicating,
quadruplicating or whatever the work. Another idea that might be feasible
this way is allowing more general exponents, say x^1/2+x^3/2+...

Best,
Chris