Question: 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

Answer: 
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](http://www.music.miami.edu/programs/mue/Research/jvandekieft/jvchapter5.htm) 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:

![number of multiplications for impulse response length of 32](https://i.stack.imgur.com/AWjo6.png)

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:

![enter image description here](https://i.stack.imgur.com/Y1cJL.png)

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>
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](http://www.youtube.com/watch?v=M0Sa8fLOajA). So, $n + 2\*n\log n = n(1+2\, \log n)$ is still a way faster than $n^2.$