Is the Fast Fourier Transform associative?

Question

For multiplying 2 polynomials, we can use the FFT:

$$IFFT(FFT(p(x)).FFT(q(x))) = p(x)*q(x)$$

Can I do

$$IFFT(FFT(p(x)).FFT(q(x)).FFT(r(x))) = p(x)*q(x)*r(x)$$ ?

Where $.$ is coefficient-wise polynomial multiplication, and $*$ is simple polynomial multiplication.

If the above is true, then I could do

$$IFFT(p(x))*IFFT(q(x))*IFFT(r(x)) = IFFT(FFT(IFFT(p(x))).FFT(IFFT(q(x))).FFT(IFFT(r(x)))) = \ IFFT(p(x).q(x).r(x)) \implies FFT(IFFT(p(x))*IFFT(q(x))*IFFT(r(x))) = p(x).q(x).r(x)$$

I tried to use the relaion $FFT(IFFT(p(x))*IFFT(q(x))*IFFT(r(x))) = p(x).q(x).r(x)$ but I get garbage. Is there something wrong with my reasoning?

Answer 1

In principle, your reasoning is correct. You can certainly multiply 3 (or any number of) polynomials by Fourier transforming their coefficients, multiplying coefficient-wise, and transforming back. Two notes though:

• Using the fourier->multiply->fourier trick computes the periodic convolution of two (or more) sequences of numbers. For polynomial-multiplication, you need a non-periodic convolution. In practice this means you need to add some padding to the inputs (i.e. leading zero coefficients). And the amount of padding needed increases, the more polynomials you want to multiply. My guess would be that this is your problem.
• Your notation can be improved: If $p$ is a polynomial, then $p(x)$ is a single number. So writing $FFT(p(x))$ is formally nonsensical. Also you should really write something like $\mathcal{F}$ and $\mathcal{F}^\dagger$ or $\mathcal{F}^{-1}$ instead of $FFT$ and $IFFT$, which looks quite jarring in a math context.