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

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)?

• 500 also seems way too high [in my experience]. I've seen straightforward FFT filters win against straighforward time-domain convolution filters on x86_64 with complex samples and real-valued taps at around 64-ish taps. Jan 28, 2021 at 21:09

2 Answers

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

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

• From your plot it seems that the fft is more efficient even for array sizes < 500. I would say even for ~100. Jan 29, 2021 at 9:07
• The exact break even point depends highly on the implementation and on the processor type. These days many processor do single cycle multiplies and "number of multiplies" is not a particular good metric. A lot depends on also memory access, cache hits, pipeline stalls, vectorization (SIMD) etc. But yes, in practice the break even point is often 32, 64 or 128. Jan 29, 2021 at 12:46

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.

• Yep, that's how I determined it. 😁 Probably outdated, though, because many other changes have happened since then (pocketfft primarily) Jan 28, 2021 at 21:23