Fast algorithms for manipulating formal power series

45. R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. ACM 25 (1978), 581-595. CR 20#34535, MR 58#25090.

Abstract: dvi (3K), pdf (77K).

Paper: pdf (891K).

Abstract

The classical algorithms require order n3 operations to compute the first n terms in the reversion of a power series or the composition of two series, and order n2 log n if the fast Fourier transform (FFT) is used for power series multiplication. 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, including many standard functions of mathematical physics such as Bessel functions.

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.

Erratum

In the fourth displayed equation on page 590, the operator (curly) L is missing after the integral sign. Thanks to Kenneth Oksanen for noticing this.

Comments

The results were first announced in Brent and Kung [29]. The multivariate case is considered in Brent and Kung [39]. and generalized composition is considered in Brent and Traub [50].

For more recent related work and references, see:

Go to next publication

Return to Richard Brent's index page