## 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*) = *p*_{1}*s* +
*p*_{2}*s*^{2} + ... and
Q(*s*) = *q*_{1}*s* +
*q*_{2}*s*^{2} + ...
be formal power series.
The * composition * of Q and P is the power series
R(*s*) = *r*_{1}*s* + ...
such that R(*s*) = Q(P(*s*)).

The * composition problem * is to compute
*r*_{0}, ... , *r*_{n},
given
*p*_{1}, ... , *p*_{n}
and
*q*_{0}, ... , *q*_{n}.

The * functional inverse * of P is the power series
V(*t*) = *v*_{1}*t* +
*v*_{2}*t*^{2} + ...
such that P(V(*t*)) = *t* or
V(P(*s*) = *s*.

The * reversion problem * is to compute
*v*_{1}, ... , *v*_{n},
given
*p*_{1}, ... , *p*_{n}.

The classical algorithms for both the composition and reversion problems
require of order *n*^{3} 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