Fast Algorithms for Manipulating Formal Power Series

Abstract

The classical algorithms require order n ~ operations to compute the first n terms in the reversion of a power series or the composition of two series, and order nelog n operations if the fast Founer transform is used for power series multiplication In this paper we show that the composition and reversion problems are equivalent (up to constant factors), and we give algorithms which require only order (n log n) ~/2 operations In many cases of practical importance only order n log n operations are required, these include certain special functions of power series and power series solution of certain differential equations Applications to root-finding methods which use inverse mterpolauon and to queuemg theory are described, some results on multivariate power series are stated, and several open questions are mentioned KEY WORDS AND PHRASES formal power series, reversion of power series, composition of power series, computational complexity, fast algorithms, special functions of power series, power series solution of dlfferentml equations, queuetng theory, fast Fourier transform CRCATEGORIES 57,5 15,5 17