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

Let P, Q be formal power series in a variable t over an infinite field K, \(P(0)=0\). The composition problem is the task of computing the coefficients of the polynomial \(Q\circ P\) mod \(t^{n+1}\) given the first \(n+1\) coefficients of P and Q. The best known upper bound for the Ostrowski complexity of this problem is reached by an \(O(n^{3/2}(\log n)^{1/2})\) algorithm due to Brent and Kung. On the other hand no nonlinear lower bound is known so far. The author shows that the composition problem is essentially equivalent to computing only the nth coefficient of \(Q\circ P\). A second result determines the complexity of an approximate version. It is shown that the complexity of computing \(Q\circ P\) mod\(\prod^{n}_{i=0}(t-\epsilon_ i)\) \((\epsilon_ 0,...,\epsilon_ n\in K^{\times}\) pairwise different) is of order n log n.