formal power series

[Paul Zimmermann]

Keith,

   We have several projects built on top of gmp, but I don't see a formal power series package anywhere.
   This is despite some of our esteemed developers writing papers about fast algorithms for such problems.
   I would find such a package very useful, and in fact have written prototypes, but I'm never happy with what I 
   produce.   Has anyone else tried?   Some relevant thoughts:

Which type of coefficients do you have in mind?
Probably you also want polynomials.

   1. probably we want rational coefficients in general, but for exponential generating functions it might be preferable
   to make the factorial implicit.

You may choose the type at compile time.

   2. we have plenty of fast algorithms in the literature (Brent, Traub, Henrici, Bernstein, Zimmermann, ...) including
   FFT and Newton-based methods.   But has anybody ever done a test to see how long a series has to be in practice
   for these to win?   In combinatorics applications, the coefficients can get huge, so it doesn't make sense to assume
   a constant time for all scalar operations.

You'll find on <http://www.loria.fr/~zimmerma/papers/MP.mpl> a Maple package
that implements fast operations using the "middle product". We found the
threshold with the (highly optimized) native operations was quite small:

    |\^/|     Maple 9.5 (IBM INTEL LINUX)
._|\|   |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple Inc. 2004
 \  MAPLE  /  All rights reserved. Maple is a trademark of
 <____ ____>  Waterloo Maple Inc.
      |       Type ? for help.
> read `MP.mpl`;
checking MP routines...everything seems ok.
> c:=series(cos(x), x, 100):
> st:=time(): t:=MP[Sqrt](c): time()-st;  
                                     0.236

> st:=time(): t2:=series(c^(1/2),x,100): time()-st;
                                     1.173

> t-t2;
                                       0

   3. could we mimic the gmp design, with a lower layer like mpn, and then a user layer?

If you want a generic implementation, you should first look at software
like Synaps or Mathemagix.

   4. I'd like to solve implicit and functional equations, not just do the standard + - * / exp log sqrt etc.

The author of Mathemagix (Joris van der Hoeven) is the right person to ask.

   5. We might need a sparse representation to store things like x^n*f(x^m) (with big n and m) efficiently.

Paul