O((n log n)3/2) algorithms for composition and reversion of power series

29. R. P. Brent and H. T. Kung, O((n log n)3/2) algorithms for composition and reversion of power series, in Analytic Computational Complexity (edited by J. F. Traub), Academic Press, New York, 1975, 217-225. MR 52#15938, 55#1699.

Paper: pdf (483K).

Abstract

Let P(s) = p1s +  p2s2 + ... and Q(s) = q1s +  q2s2 + ... be formal power series.

The composition of Q and P is the power series R(s) = r1s + ... such that R(s) = Q(P(s)).
The composition problem is to compute r0, ... , rn, given p1, ... , pn and q0, ... , qn.

The functional inverse of P is the power series V(t) = v1t +  v2t2 + ... such that P(V(t)) = t or V(P(s) = s.
The reversion problem is to compute v1, ... , vn, given p1, ... , pn.

The classical algorithms for both the composition and reversion problems require of order n3 operations. We describe algorithms which can solve both problems in O((n log n)3/2) operations.

Comments

This was a preliminary announcement of the main results regarding composition and reversion of power series in one variable. An extended version was published as Brent and Kung [45]. The multivariate case was later considered in Brent and Kung [39].

Go to next publication

Return to Richard Brent's index page