On the Complexity of Composition and Generalized Composition of Power Series

Publisher Website
Google Scholar
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 log2 q times that of a single composition. Brent (1) showed that the factor log2 q can be eliminated in the computation of the first n terms of (F(x))q by a change of representation, using the logarithm and exponential functions. We show here that the factor log2 q 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. We conclude the paper with some open problems.

This publication has 11 references indexed in Scilit: