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) = f1x +  f2x2 + ... 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 log2q times that of a single composition. Brent [28] showed that the factor log2q 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 log2q 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