# 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. – Marcus Müller Jan 28 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. – orbit Jan 29 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. – Hilmar Jan 29 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) – endolith Jan 28 at 21:23