What is the reason that is FFT multiplication slower than other methods for small N?

Question

I've seen plenty of statements in papers and on websites that Fast Fourier Transform-based multiplication algorithms are slower than other multiplication algorithms for relatively small input size N, and I've seen plenty of data in papers and on websites demonstrating that this is the case, but nothing I've come across has bothered to explain what causes FFT to be slower for small N.

I would guess that the overhead is due to getting the input into a form that FFT can swallow, but I'd like to know what the actual cause of the overhead is and whether it can be reduced. Note that I'm not talking about switching from some FFT implementation to another method when N is below a certain size as many implementations do, but the source of overhead in the FFT itself and what can be done to reduce it.

Answer 1

The Wikipedia FFT article says that the split-radix FFT algorithm requires $4N\log_2N-6N+8$ real multiplications and additions. Multiplying 2 degree $M$ polynomials results in a polynomial of degree $2M$, so the "FFT multiplication of two polynomials" goes like this:

FFT (size 2M) of polynomial f(x) (evaluate f(x) at the 2M primitive roots of unity)
FFT (size 2M) of polynomial g(x) (evaluate g(x) at the 2M primitive roots of unity)
multiply each of the 2M fourier coefficients together
inverse FFT (size 2M) of the fourier coefficients to get the resulting polynomial

Perhaps there is a way to make the first two FFTs faster based on the fact that the $M+1$th through $2M$th coefficients of f(x) and g(x) are all zeros, but I don't know it offhand.

So we are doing 3 FFTs of size $2M$ plus an additional $2M$ complex multiplies (each of which is 4 real multiplies and 2 real additions so: $$3 (4(2M)\lg2M - 6(2M)+8)+4M = 24M\lg M -8M+24$$ additions and $24M\lg M - 4M + 24$ multiplications.

Meanwhile the naive polynomial multiplication algorithm (convolution) takes $M^2$ real multiplications and $(M-1)^2$ real additions. (Proof left as exercise for the reader.)

Thus the naive algorithm will be faster for $M \leq 128$, while the FFT based algorithm will probably be faster at $M \geq 256$, and the crossover will be somewhere between 128 and 256. (Proof left as exercise for the reader.)

I did this quickly and sloppily, so I'm probably off somewhere (e.g., the forward FFTs are real -> complex, (but is there a DCT version that would be cheaper?) while the reverse is complex -> real (which may have slightly different constants than the ones I used,) and I only did the evaluation at $M$ power of 2 (FFT of non-power of 2s is more expensive.)) Nonetheless, the point stands: the constant multiplier for the FFT is approximately 24, while the constant multiplier for the naive convolution is 1, so you need to compare (something like) $24M\lg M$ to $M^2$.