I am looking for an efficient way of calculating the first $n$ terms of series expansion of $e^{p(x)}$ for a polynomial $p(x)$. Ideally something that runs in $O(n \log n)$.
I already know how to do several other operations in $O(n \log n)$, or more precisely in $M(n)$ where $M(n)$ is the complexity of polynomial multiplication:
- Multiplication; this is by definition
- Inverse (and consequently division); by doubling the number of terms of the inverse in each step (as I explained here)
- $ln(p(x)) = \int \frac{p'(x)}{p(x)} d x$; directly per formula by doing a derivative, division and then integration in that order
The following can be trivialy done in linear time:
- Addition / Subtraction
- Derivative / Integral
One of the things I am still missing is $exp(p(x))$. This is where I got so far:
$$ p(x) = \sum_{k=0}^{n-1} a_k x^k $$
\begin{align} exp(p(x)) &= exp( \sum_{k=0}^{n-1} a_k x^k ) \\ &= \prod_{k=0}^{n-1} exp( a_k x^k ) \\ &= \prod_{k=0}^{n-1} q_k(x) \end{align}
\begin{align} q_k(x) &= exp(a_k x^k) \\ &= \sum_{i=0}^{\frac{n-1}{k}} \frac{(a_k x^k)^i}{i!} + O(x^n) \end{align}
So, for each term $a_k x^k$ we get a polynomial $q_k(x)$ with $\lfloor n/k \rfloor$ non-zero terms. The non-zero terms are precisely those at positions which is a multiple of $k$.
Now we need to multiply all of them efficiently. One way I can think of would be to do the following. Take the polynomials $q_k(x)$ starting from the largest $k$ first (from $n$ to $1$). For each $q_k(x)$, find the largest proper divisor $d$ of $k$. We can then multiply $q_k(x)$ and $q_d(x)$ and replace both with their product which is going to have the same form as $q_d(x)$. I.e. only coefficients at the positions that are multiple of $d$ are going to be non-zero. A single such multiplication can be done in $O(\frac{k}{d} M(\frac{n}{k}))$ as explained here. The total complexity of combining all of those $k$ polynomials in such a way is then $\sum_{k=2}^{n-1} \frac{k}{d_k} M(\frac{n}{k})$ which asymptotically seems to grow as $O(\frac{n^2}{\log n})$ if $M(n) = O(n \log n)$.
I am not sure that the aforementioned $O(\frac{n^2}{\log n})$ algorithm can be improved to $O(n \log n)$. If an $O(n \log n)$ algorithm exists, it might very well be based on a completely different approach. Any ideas?
Okay, I found an $O(n \log n)$ algorithm in R.P.Brent & H.T.Kung - Fast Algorithms for Manipulating Formal Power Series.
I implemented it in Altruct.