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