Saturday, July 18, 2009

How fast can you expand a polynomial?

I just came across the following very basic problem.
given a expression of univariable polynomial which is constructed by the following recursion rules
(1) A constant or the variable x is a EXPRESSION.
(2) The sum of two EXPRESSIONS is a EXPRESSION
(3) The product of two EXPRESSION is a EXPRESSION
e.g.
f(x)=((1+x+x^2)(x^2+2x^3)+x^3(2+3x^4))(1+2x)

We know the degree of the polynomial and the length of the EXPRESSION are of sizes O(n).
The question is how fast can you expand the EXPRESSION into a standard form, i.e.,
\sum_{i=0}^n c_i x^i
In an other word, how fast can you compute the coefficients c_i for all i.

It is pretty trivial to achieve O(n^3). (the running time analysis needs a bit counting).
With the help of FFT(fast Fourier transformation), you can do O(n^2\log^2n).
I think I can do O(n^2), but need some nontrivial math...

My question is whether \Omega(n^2) is the lower bound..
or can we do even better?
Could anyone point me out some reference??

No comments:

Post a Comment