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