series and expansion.

[Richard B. Kreckel]

Chris,

Find below some immature thoughts about what IMHO needs to be addressed in
order to construct a more veratile series expansion.

On Wed, 16 Jun 2004, Chris Dams wrote:
[...]
> 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 suspect that unless those polynomials are expanded, even the current
ldegree could fall into the trap of a vanishing leading coefficient?

>                                     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.

Yes, efficient in time.  I'm not so sure about efficiency in space,
however.  The reason is that currently we go ahead differentiating and
later insert the expansion point.  When that insertion happens, the series
coefficients usually collapse considerably.  When we extract term by term
from the stream of coefficients, that insertion might not be desireable.
If f(x) and g(x) have both been exanded at x==a up to O(x^2), then we
have the coefficients f(a), f'(a), f''(a), g(a), g'(a) and g''(a).  The
streams should hold f''(x) and g''(x) for subsequent computation of higher
coefficients.  This is not so bad yet, but if we want to compute (f*g)(x)
up to order x^2 we can readily assemble the following terms:

    (f*g)(x)|x==a == f(a)*g(a)
                   + (f'(a)*g(a) + f(a)*g'(a)) * x
                   + (f''(a)*g(a) + 2f'(a)*g'(a) + f(a)*g''(a))/2! * x^2

In addition we would like to also store (f*g)''(x) in order to
subsequently extract higher coefficients.  However, that is not possible,
since it contains f(x), g(x), f'(x) and g'(x) which are not available any
more.  Remember, we have already .subs(x==a)!  Only f(a), g(a), f'(a) and
g'(a) are available.  So, we would have to store the unsubstituted
coefficients as well, which leads to some degree of bloat.

But if the series stream objects where the terms are extracted from have
controlled lifetime it might not hurt at all?

>       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+...

Puiseux series are interesting, but they might also be feasible without
term-by-term extraction?  They aggravate one open question which must be
addressed anyways for term-by-term extraction.  If one coefficient
vanishes, what is supposed to happen?  Clearly, we shouldn't skip to the
next coefficient because this leads to an infinite loop if the series
turns out to be terminating.  So, zero should be returned.  In the case of
Puiseux series, this would require us to be able to foresay what the next
term ought to be, is it x^1 or x^3/2 or x^5/4?  If we know the common
denominator of all exponents of x in the series (4 in the example above)
before starting the actual computation, then there is no problem.

Regards
     -richy.

PS: BTW, are you aware of Joris van der Hoeven's work on this topic, e.g.
    <http://www.math.u-psud.fr/~vdhoeven/Publs/2002/relax4.ps.gz>?
-- 
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>