Why is FFT-based convolution efficient only for signals of large size?

Question

According to the documentation of scipy.signal.fftconvolve

This is generally much faster than convolve for large arrays (n > ~500), but can be slower when only a few output values are needed, and can only output float arrays (int or object array inputs will be cast to float).

Why does fft-based convolution is efficient only for large signals and how large they have to be (why the choice n > 500 is used)?

Answer 1

Say that you want to calculate a convolution $y(n) = x(n)*h(n)$. The lengths of $x(n)$ and $h(n)$ are respectively $L$ and $M$. For a linear convolution, the total number of multiplications is $m_d = LM$. If $h(n)$ is linear phase, half multiplications can be saved according to the fact that $h(n) = \pm h(M-1-n)$. So for a direct convolution,

$$m_d=LM/2$$

If you want to use FFT instead, the FFT size $N$ must satisfy $N\geq L+M-1$ to prevent aliasing. In this case, you have to do 2 N-point FFTs, 1 N-point IFFT and 1 N-point multiplication. The total number of multiplications is

$$ m_F=\frac{3}{2} N\log_2N+N=N(1+\frac{3}{2}\log_2N) $$

The ratio between $m_d$ and $m_F$ is

$$ K_m=\frac{m_d}{m_F}=\frac{ML}{2N(1+\frac{3}{2}\log_2N)}=\frac{ML}{2(M+L-1)\Big[1+\frac{3}{2}\log_2(M+L-1)\Big]} $$

The equation above will be discussed in two situations.

1. If $x(n)$ and $h(n)$ have similar lengths, so suppose that $M=L$, and $N=2M-1\approx 2M$. We have

$$ K_m=\frac{M}{4(\frac{5}{2}+\frac{3}{2}\log_2M)}=\frac{M}{10+6\log_2M} $$

The longer $x(n)$ and $h(n)$, the larger $K_m$, and the FFT-based convolution is much more efficient. The following figure shows $K_m$ varying against $M$.

2. If $x(n)$ is very long, i.e., $L\gg M$, and $N = L+M-1\approx L$, we can derive that

$$ K_m = \frac{M}{2+3\log_2L} $$

It can be seen that when $L$ is too large, $K_m$ decreases and the outperformance of circular convolution is covered up. Therefore, we have to split the long input signal into pieces and apply fast convolution in sequence. The most well-known methods are overlap-add and overlap-save.

Answer 2

The direct convolution approach has a complexity proportional to $n^2$

The FFT based approach has complexity $n \log(n)$.

Since there are unknown pre-factors and the complexity only holds asymptotically, the only thing one can infer from the complexities is that only for large enough $n$ the FFT approach becomes more efficient.

The $n=500$ threshold is thus probably determined empirically.