Extraction of Coefficients in the Exponential Function of a Series

Question

Question: Let $f(x) \in x\mathbb{C}[[x]]$. What is the (asymptotically) fastest algorithm for calculating the coefficient of $x^n$ in $e^{f(x)}$?

Naive Solution 1: Using fast polynomial multiplication (I assume it takes $O(n \log n)$ time to multiply two polynomials of degree $n$), one can solve this problem with complexity of $O(n^2 \log n)$ by writing $[x^n]e^{f}$ as $[x^n]\sum_{i=n}^{\infty} \frac{f^i}{i!}$, and calculate the (truncated) first $n$'th powers of $f$.

Naive Solution 2: This solution utilizes the multicativity of the exponential function. One writes $[x^n]e^f$ as $[x^n] \prod_{i=1}^{n} e^{([x^i]f) \cdot x^i} = [x^n] \prod_{i=1}^{n} (\sum_{j=0}^{n/i} \frac{([x^i]f)^j x^{ij}}{j!})$, and then multiplies $n$ polynomials of degree $n$.

Can one do better (asymptotically)?

Although the example $e^f$ has actually occurred in a calculation I am doing, and the exponential function is abundant in combinatorics, a further natural generalization is: Are there some nice non-rational elementary functions, such as $g(x):-\log(1-x)$, for which $[x^n](g \circ f)$ can be computed faster than $O(n^2 \log n)$?

Answer 1

It can be done with $O(1)$ polynomial multiplications, i.e. $O(n \log n)$ with your assumptions. One uses Newton's method to invert the logarithm of a power series. The logarithm is computed using $O(1)$ polynomial multiplications as

$$\log(f(x)) = \int \frac{f'(x)}{f(x)}.$$

More generally, one can use similar techniques to evaluate the compositions $g(f(x))$ or $f(g(x))$ rapidly, where $g$ is any function satisfying a sufficiently nice differential equation.

The paper Igor Rivin linked to is a good reference, but just to clarify, this classical result goes back to Brent and Kung (1978). In recent years, several papers have been published that push down the $O(1)$ constant. David Harvey obtained a bound of $13/6 + o(1)$ polynomial multiplications for the exponential of a power series (see http://web.maths.unsw.edu.au/~davidharvey/papers/fast-exp/index.html), but I'm not sure if this is still the record.

It's worth nothing that there is a Naive Solution 0 that requires $O(n^2)$ operations: the coefficients of $g(x) = e^{f(x)}$ satisfy the recursion

$$[x^k] g = \frac{1}{k}\sum_{j=1}^k j ([x^j]f) ([x^{k-j}] g).$$

Indeed, if $f$ is a polynomial of degree $m$, this algorithm only requires $O(mn)$ operations, which is superior to the other methods if $m = o(\log n)$. The classical division algorithm gives a similar $O(mn)$ method for the logarithm of a power series.

Another remark is that your Naive Solution 2 can be modified to get down to $O(n \log^3 n)$ complexity, using a divide and conquer approach.

All these algorithms actually require you to compute the first $n$ coefficients. As far as I know, it is an open problem whether extracting a single coefficient can be done faster (by more than a constant factor). I believe this is an open problem even for reciprocal of power series.

Answer 2

This question (and many related ones) is answered in this paper of Bostan, Salvy, and Schost.