2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is relevant to other algorithms as well: an algorithm with a "bad" asymtotic runtime can be much faster than a fancier and theoretically faster algorithm on small inputs. For example, insertion sort can be a much better choice for small arrays than quicksort. $\endgroup$ – Juho May 9 '14 at 14:45
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Nice answer. So what your saying is that the total number of operations required by the FFT that are not significantly affected by the size of $N$ (the constants $24$, $8$ and $4$) are simply large enough that for small $N$ they are going to take longer than $N^2$ for much the same reason that $10x > x^2$ for $x < 10$. $\endgroup$ – hatch22 May 10 '14 at 19:13
  • $\begingroup$ yes, although I was also trying to answer your question about why the constant is 24 (because you have to do 3 FFTs of size 2N with complex arithmetic.) $\endgroup$ – Wandering Logic May 10 '14 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.