Relax, but don't be too lazy


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