Why is fftfilt (i.e. fft of both inputs, then element-wise multiplication, then ifft) faster than direct convolution?

I have the following matlab code

N = 500;
M = 32;
K = N + M - 1; % Length of full convolution

x = randn(N);
y = ones(M);

% first one: convolution
r = conv(x, y, 'same');

% second one: multiplication
z = ifft(fft(x, K, K).*fft(y, K, K));
idx = round((K-N)/2+1):round((K+N)/2); % Indices of the central portion
z = z(idx); % Obtaining the central part of the result


May I know which opertation is faster? getting $r$ or $z$? Why is this so? Thanks in advance

• if your filter is similar size to the signal: direct-convolution computation grows with approximately O(n^2) vs fft-filtering computation grows with O(n + 2 * n * log2(n)). For more reading: ccrma.stanford.edu/~jos/sasp/FFT_versus_Direct_Convolution.html . if your filter is much-much smaller than the signal: then direct-convolution grows with O(n) vs fft-filtering still growing with O(n + 2 * n * log2(n)). – Trevor Boyd Smith Dec 11 '18 at 21:18

Whether the direct convolution or the FFT/IFFT method is faster depends on the length of the impulse response, $$N_\mathrm{i}$$ and the signal length $$N_\mathrm{s}$$. With the formulas taken from here I've created a small Matlab script that calculates the required number of real multiplications and additions for the direct convolution and FFT/IFFT method, respectively. I've assumed real-valued impulse response and signal. Taking your example of $$N_\mathrm{i}=32$$ (or the other way round, this makes no difference), the direct convolution always requires less multiplications:

But if we increase $$N_\mathrm{i}$$ to 50, for example, the direct convolution requires less multiplications up to a signal length of about 60. For signal length greater than 60 the FFT/IFFT method requires less multiplications:

The actual computation time depends on some other parameters, especially the CPU architecture but the number of multplications is usually a good indicator.

The MATLAB code for the above figures for reference:

Ns = 1:1000; % length of signal
Ni = 50; % length of impulse response

K = Ni + Ns - 1;

% number of real multiplications for convolution:
M_R_conv = Ns*Ni;
% number of real multiplications for convolution:
A_R_conv = Ns*(Ni-1);

% number of complex multiplications for freq domain conv:
M_C_dft = 3/4 * K .* (log2(K) + 1) + K;
% number of complex additions for freq domain conv:
A_C_dft = 3/2 * K .* log2(K);

% number of real multiplications for freq domain conv:
M_R_dft = 4*M_C_dft;
% number of real additions for freq domain conv:
A_C_dft = 2 * A_C_dft + 2 * M_R_dft;

figure('Position', [0 0 400 300]);
plot(M_R_conv, 'b');
hold on;
plot(M_R_dft, 'r');
hold off;
legend('direct', 'fft', 'location', 'Southeast');
title(['number of real multiplications. Ni: ' num2str(Ni)]);
xlabel('length of signal');


A sidenote to your code: as it stands it is not running as you're creating NxN and MxM matrices for x and y. What you probably want to do is

x = rand(1,N);
y = ones(1, M)
% ...
z = ifft(fft(x, K).*fft(y, K));


p.s. for those of you interested in Python code instead of Matlab, here is the same code in Python: https://gitlab.com/snippets/1789085

• yeah, i thought so. However, when I ran it in Matlab, calculating z is slower than calculating r. Can you try it and tell my your result? – freak_warrior Dec 13 '13 at 9:13
• If your question actually is "why is convolution faster here?" then you should rephrase you post accordingly. – Deve Dec 13 '13 at 9:28
• thanks! edited. Anyway did you try the code on Matlab? – freak_warrior Dec 13 '13 at 9:49
• For small number of N and M the time measurement varies. But try N = M = 1e6 and you will get a large speed up through FFT. I will provide an detailed answer shortly. – Deve Dec 13 '13 at 12:33

I think that the question is actually not why $n$ elementary multiplications is faster than $n^2$ ones. A convolution means that you multiply a vector with a convolution matrix. The operation has complexity $O(n^2)$. Yet, you can translate the vectors into frequency domain, where the convolution is diagonal matrix and you simply multiply $n$ corresponding elements of the vectors. The question is why is it faster despite of additional foruier and inverse fourier conversions, which is applying a matrix to the vectors, which has normally overhead of $n^2$. The answer is that the Fast Fourier transform is faster. FFT takes $n\log n$ elementary multiplications. So, $n + 2*n\log n = n(1+2\, \log n)$ is still a way faster than $n^2.$

• The FFT/IFFT method is only faster if $n(1+2\log n) < n^2$, see my answer. The above inequality does not hold for $n=5$, for example. – Deve Dec 14 '13 at 10:46
• @Deve The question why faster implies that $n(1+2\log n)<n^2.$ See my answer. – Val Dec 14 '13 at 11:08

fast convolution wouldn't be faster if the "fast" fourier transform (FFT) was not used.

BTW, i need to figure out how to use math pasteup here. it is LaTeX or something else? where is the information on that?