A fast numerical algorithm for the composition of power series with complex coefficients

AbstractThe composition problem for univariate complex power series P, Q (i.e., the computation of the first n + 1 coefficients of the composition Q ° P) is numerically solved by interpolation methods. Using multitape Turing machines as a model of computation, the composition problem of power series with integer coefficients of modulus ⩽ν, ⩾n, is possible in time O(ψ(n2 log n log ν)), where ψ(m) bounds the amount of time for the multiplication of m-bit numbers (e.g., ψ(m) = cm log(m + 1) log log(m + 2) for multitape Turing machines). This algorithm is asymptotically faster than an implementation of the Brent-Kung algorithm on a multitape Turing machine; the improvement is of order n12 (up to logarithmic terms)