I'm exploring the use of FFTs for multiplication, but even with simple examples it seems to go wrong. For example, here I'm trying to multiply $1$ by $2x$ (code is in matlab, but I think you can probably understand it even if you don't know the language):
# x and y are two polynomials, x(n) = 1; y(n) = 2n
x = [0 0 0 1];
y = [0 0 2 0];
# Evaluate both polynomials at roots of unity
xval = fft(x);
yval = fft(y);
# zval(n) = x(n)*y(n)
zval = xval .* yval;
# interpolate to get back prodvec(n) = x(n)*y(n)
prodvec = ifft(zval) / length(zval);
This gives an output of [0 0 0 .5]
instead of [0 0 2 0]
. Any idea what I'm doing wrong? It seems obvious enough that I should be doing $Wx$ to find the values of $x(n)$, and then $W^{-1}z$ will give me back the polynomial I want. But it's not working.