## Fast algorithms for manipulating formal power series

50. R. P. Brent and
J. F. Traub,
On the complexity of composition and generalized composition of power series,
* SIAM J. Computing * 9 (1980), 54-66.
MR 81b:68042.
Abstract:
dvi (3K),
pdf (82K),
ps (28K),

Paper:
pdf (942K).

## Abstract

Let F(*x*) = *f*_{1}*x* +
*f*_{2}*x*^{2} + ...
be a formal power series over a
field.
Let F^{(0)}(*x*) = *x* and,
for *q* = 1, 2, ..., define
F^{(q)}(*x*) = F^{(q-1)}(F(*x*)).
The obvious algorithm for computing the
first *n* terms of F^{(q)}(*x*)
is by the composition analogue of repeated squaring.
This algorithm has complexity about log_{2}*q* times
that of a single composition.
Brent [28] showed that the factor
log_{2}*q*
can be eliminated in the computation of the first *n* terms of
the power (F(*x*))^{q}
by a change of representation, using the logarithm and exponential
functions. We show here that the factor
log_{2}*q*
can also be eliminated for
the composition problem, unless the complexity of composition is
quasi-linear.

F^{(q)}(*x*)
can often, but not always, be defined for more general *q*.
We give algorithms and complexity bounds for computing the first
*n* terms of
F^{(q)}(*x*) whenever it is defined.

The paper concludes with some open problems.

## Errata

We thank Keith Briggs for pointing out two typographical errors
in the original paper [corrections made in the online version].
Page 63, line 13, in Algorithm 5.1,
"((-*R*" should be "(-*R*".

Page 63, line 21, in Algorithm 5.2,
the German letter should be a "B".

## Comments

For related work, see Brent and Kung
[45].
Go to next publication

Return to Richard Brent's index page