4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)). $\endgroup$ – Trevor Boyd Smith Dec 11 '18 at 21:18
8
$\begingroup$

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:

number of multiplications for impulse response length of 32

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

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – freak_warrior Dec 13 '13 at 9:13
  • $\begingroup$ If your question actually is "why is convolution faster here?" then you should rephrase you post accordingly. $\endgroup$ – Deve Dec 13 '13 at 9:28
  • $\begingroup$ thanks! edited. Anyway did you try the code on Matlab? $\endgroup$ – freak_warrior Dec 13 '13 at 9:49
  • $\begingroup$ 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. $\endgroup$ – Deve Dec 13 '13 at 12:33
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Deve Dec 14 '13 at 10:46
  • $\begingroup$ @Deve The question why faster implies that $n(1+2\log n)<n^2.$ See my answer. $\endgroup$ – Val Dec 14 '13 at 11:08
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.