1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.