Fast Algorithms for Manipulating Formal Power Series.

摘要

The classical algorithms require O(n sup 3) operations to compute the first n terms in the reversion of a power series or the composition of two series,and O((n sup 2) log n) operations if the fast Fourier 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 O((n log n) sup 3/2) operations. In many cases of practical importance only O(n log n) operations are required. An application to root-finding methods which use inverse interpolation is described,some results on multivariate power series are stated,and several open questions are mentioned.