[ Homepage | Publications | Talks | TeXmacs |
Mathemagix ] |

Assume that we wish to expand the product
of two formal power series
and . Classically, there are
two types of algorithms to do this: *zealous* algorithms first
expand and up to order ,
multiply the results and truncate at order .
*Lazy* algorithms on the contrary compute the coefficients of and
gradually and they perform no more computations than strictly necessary
at each stage. In particular, at the moment we compute the coefficient
of in ,
only and are known.

Lazy algorithms have the advantage that the coefficients of and may actually depend on “previous” coefficients of , as long as they are computed before they are needed in the multiplication. I.e. the coefficients and may depend on . For this reason, lazy algorithms are extremely useful when solving functional equations in rings of formal power series. However, lazy algorithms have the disadvantage that the classical asymptotically fast multiplication algorithms on polynomials — such as the divide and conquer algorithm and fast Fourier multiplication — can not be used.

In a previous paper, we therefore introduced *relaxed* algorithms,
which share the property concerning the resolution of functional
equations with lazy algorithms, but perform slightly more computations
than lazy algorithms during the computation of a given coefficient of
. These extra computations
anticipate the computations of the next coefficients of and dramatically improve the asymptotic time
complexities of such algorithms.

In this paper, we survey several classical and new zealous algorithms for manipulating formal power series, including algorithms for multiplication, division, resolution of differential equations, composition and reversion. Next, we give various relaxed algorithms for these operations. All algorithms are specified in great detail and we prove theoretical time and space complexity bounds. Most algorithms have been experimentally implemented in C++ and we provide benchmarks. We conclude by some suggestions for future developments and a discussion of the fitness of the lazy and relaxed approaches for specific applications.

The paper is intended both for those who are interested in the most recent algorithms for the manipulation of formal power series and for those who want to actually implement a power series library into a computer algebra system.

**View:** Gzipped Postscript, BibTeX