On the Complexity of Composition and Generalized Composition of Power Series
Richard P. Brent, Joseph F. Traub · SIAM Journal on Computing · 1980
Let $F(x) = f_1 x + f_2 x^2 + \cdots $ be a formal power series over a field $\Delta $ Let $F^{[0]} (x) = x$ and for $q = 1,2, \cdots $ , 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 $\log _2 q$ times that of a single composition. Brent showed that the factor $\log _2 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 the factor $\log _2 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.