Why is `fftfilt` (i.e. `fft` of both inputs, then element-wise multiplication, then `ifft`) faster than direct convolution?
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