References

The classical algorithms require order n 3 operations to compute the first n terms in the reversion of a power series or the composition of two series, and order n 2 log n 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 order (n log n) 3/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 solutions of certain differential equations. Applications to root-finding methods which use inverse interpolation and to queueing theory are described, some results on multivariate power series are stated, and several open questions are mentioned. Comments Only the Abstract is given here. The results were announced in [1], and the full paper appeared as [3]. The multivariate case is considered in [2], and generalized composition is considered in [4]