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.
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.
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.
In the fourth displayed equation on page 590, the operator (curly) L is
missing after the integral sign. Thanks to Kenneth Oksanen for noticing
The results were first announced in Brent and Kung
The multivariate case is considered in Brent and Kung
and generalized composition is considered in Brent and Traub
For more recent related work and references, see:
Go to next publication
Return to Richard Brent's index page