Paper: pdf (483K).
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.
Go to next publication
Return to Richard Brent's index page