How fast can you expand a polynomial? (Cont)

I finally get some time to record the O(n^2) time algorithm.
The O(n^2\log^2 n) time algorithm can be found from the appendix of this paper of mine.

Now, let me present an O(n^2) time algorithm.

First, an EXPRESSION can be thought as a tree where all variables and constants are leaves and inner nodes are operations (* and +)

E.g. (x^2+x+1)(2x+1) corresponds to







(Algorithm 1)
1. Choose n+1 different numbers a_1, ...., a_{n+1} .
2. Evaluate the polynomial at these points, i.e., compute F(a_i). (each evaluation takes linear time (bottom-up over the tree). So O(n^2) time in total)
3. Use any O(n^2) polynomial interpolation algorithm to find the coefficient (actually reduces to finding a solution for a linear system).

Cute? Still have to rely on some other nontrivial algorithm to invert the Vandermonde system in O(n^2) time (ref [3][4] in the wiki page).

Let us look at a cuter one.
(Algorithm 2)

Suppose the polynomial if F(x)=\sum_j c_j x^j.
Let e_i be the n-dimensional zero vector except that the ith entry is 1, i.e.,e_i=(0,0,..,1,...,0,0).
Let d_i be the n-dimensional vector which is the DFT(discrete Fourier transformation) of e_i.
Denote u be the nth root of unit and u={1,u,u^2,....,u^{n-1}}.
Therefore, e_i[j]=\sum_k d_i[k] u^{jk}. Equivalently, e_i=\sum_k d_i[k] u^k
where u^k={1,u^k,u^{2k},u^{3k},.....}

Computing all d_i takes O(n^2) time.
Let c be the coefficient vector (of F).
c_i = <c, e_i> (inner product)
<c,e_i>=\sum_k d_i[k]<c, u^k>....................(1)

But what is <c,u^k> ? it is exactly the numerical value of F(u^k)!!! (think about it)

Now, we have our algorithm:
1.compute d_i for all i ....................use DFT formula directly (don't need FFT) ,O(n^2)
2.compute F(u^k) for all k.....................n poly evaluations over complex, O(n^2)
3.use (1) to compute the coefficient.................O(n^2)

So, nothing fancy here(except the idea:). Cuter, right?


OPEN question: can we do better? or the lower bound is O(n^2)