## 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 *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 (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