2
$\begingroup$

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.

1 Answers 1

3

There are two things you're doing wrong:

  1. Vectors in matlab are read left-to-right, so you should have $x,y$ reversed.
  2. The FFT and inverse FFT operations are inverses, so there's no need to divide by the normalization factor.

Try this instead:

x = [1 0 0 0]; y = [0 2 0 0]; ifft(fft(x).*fft(y)) 
  • 0
    I wanted to write the same thing, but then thought that that can't be the entire problem, since in that case the result should have been `[0 .5 0 0]` and not `[0 0 0 .5]`, no?2011-02-21
  • 0
    Also, if the OP wants to multiply polynomials having too high degree, e.g. $x^3 + x^2 + 1$ (represented by $[1, 0, 1, 1]$) and $x^3 + x + 1$ (represented by $[1, 1, 0, 1]$), make sure to use the enough points in his Fourier transform, e.g. in this case fft(x, 8) instead of just fft(x).2011-02-21
  • 0
    @joriki, have you tried the code? The reason you get $.5$ and not $2$ is because you divide by the length, which you shouldn't do, since it's built into ifft.2011-02-21
  • 0
    @Calle: That's a misunderstanding. I agreed about the $.5$ and $2$, and also about the reversing of the vectors. What I got wrong was that I thought $x^5$ would be folded to $x^1$ if the array is too short, but in fact it gets folded to $x^3$, which explains the OP's result.2011-02-21