# Is ifft(fft(x).*fft(h)) faster or conv(x,h) ?

65 views (last 30 days)

Show older comments

Dear All,

I need to find out which one is faster to obtain convolution? - Linear convolution using just 'conv'? - or Obtaining Convolution from ifft(fft)? As far as I have coded and identified using tic/toc, that Matlab performs linear convolution faster than ifft(fft). But textbooks say fft is faster.

##### 4 Comments

Alim Huseynov
on 11 Mar 2020

Edited: Rik
on 11 Mar 2020

Section 1. (for Problem 1)

format LONGENG; %increased precision

[x,fs]=audioread('africa-toto.wav');

x=x'; %Column vector was transposed for making it row vector.

yy37=[1:37]; % 37 place line vector created for further storage

h=ones(1,18); % this line vector will accept given values

h(1)=-0.0000000000000020464110886333966;

h(2)=0.020185108207322531;

h(3)=-0.0000000000000032166461686436967;

h(4)=0.0063932717248746463;

h(5)=-0.0000000000000042068450824985665;

h(6)=-0.030584021511458139;

h(7)=-0.0000000000000037927619003410752;

h(8)=0.0092608976386982338;

h(9)=-0.0000000000000034686968012612998;

h(10)=0.055319499353126252;

h(11)=-0.0000000000000029165858917179788;

h(12)=-0.062431158774528053;

h(13)=-0.0000000000000030126051803342088;

h(14)=-0.079105057829546827;

h(15)=-0.0000000000000030966220578734095;

h(16)=0.3013776867026185;

h(17)=-0.0000000000000028385702197172922;

h(18)=0.58901882620106349;

yy37(1)=0.0053712613864042745; %the value manually given because there is no y(0)

yy37(2:19)=h; %line vector copied to filter coefficients

for i=1:18 % for loop used for the rest of values.

yy37(19+i)=yy37(19-i);

end

t = zeros(1,100); % Vector for storing time values

for n = 1:100 %Looping repeats 100 times

tic; % Timer started

x_c=conv(x,yy37); %Operation of convolution

t(n)=toc; %During each loop relevant value of timer will be copied and timer will be reset

end

t_aver=mean(t); %Average time spent for operation

********************************************************************************

Section 2A (Problem 2)

format LONGENG; %increased precision

[x,fs]=audioread('africa-toto.wav');

x=x'; %Column vector was transposed for making it row vector.

yy37=[1:37]; % 37 place line vector created for further storage

h=ones(1,18); % this line vector will accept given values

h(1)=-0.0000000000000020464110886333966;

h(2)=0.020185108207322531;

h(3)=-0.0000000000000032166461686436967;

h(4)=0.0063932717248746463;

h(5)=-0.0000000000000042068450824985665;

h(6)=-0.030584021511458139;

h(7)=-0.0000000000000037927619003410752;

h(8)=0.0092608976386982338;

h(9)=-0.0000000000000034686968012612998;

h(10)=0.055319499353126252;

h(11)=-0.0000000000000029165858917179788;

h(12)=-0.062431158774528053;

h(13)=-0.0000000000000030126051803342088;

h(14)=-0.079105057829546827;

h(15)=-0.0000000000000030966220578734095;

h(16)=0.3013776867026185;

h(17)=-0.0000000000000028385702197172922;

h(18)=0.58901882620106349;

yy37(1)=0.0053712613864042745; %the value manually given because there is no y(0)

yy37(2:19)=h; %line vector copied to filter coefficients

for i=1:18 % for loop used for the rest of values.

yy37(19+i)=yy37(19-i);

end

t = zeros(1,100); % Vector for storing time values

yy37Pad=[yy37 zeros(1,length(x)-1)]; %Zero Padding

xPad=[x zeros(1,length(yy37)-1)]; %Zero Padding

for n = 1:100 %Looping repeats 100 times

tic; % Timer started

x_c2=ifft(fft(xPad).*fft(yy37Pad)); % Obtaining inverse transform of fft of data set.

t(n)=toc;

end

t_aver=mean(t); %Average time spent for operation

*******************************************************************************

Section 2B (Problem 2)

x = randi([1 1000],1,10000);

y = randi([1 1000],1,10000);

time1=zeros(1,20);

time2=zeros(1,20);

n = length(x) + length(y) - 1;

for i=1:10

tic

z1 = conv(x,y);

time1(i)=toc;

end

for i=1:10

tic

z2 = ifft(fft(x,n) .* fft(y,n));

time2(i)=toc;

end

t1_normal=mean(time1)

t2_fft=mean(time2)

*******************************************************************************

Section 2C (Problem 2)

x = randi([1 100],1,10000);

y = randi([1 100],1,10000);

time1=zeros(1,5);

time2=zeros(1,5);

time_l=zeros(1,1000);

time_2=zeros(1,1000);

for b=1:2000

y1=y(1:b*5);

for i=1:5

tic

z1 = conv(x,y1);

time1(i)=toc;

end

n = length(x) + length(y1) - 1;

for i=1:5

tic

z2 = ifft(fft(x,n) .* fft(y1,n));

time2(i)=toc;

end

time_1(b)=mean(time1);

time_2(b)=mean(time2);

end

figure(1)

plot(5*[1:2000],time_1,'r')

hold on

plot(5*[1:2000],time_2,'g')

legend('normal','fft')

xlabel('Length of second signal')

ylabel('Time spent')

set(findall(gcf,'-property','FontSize'),'FontSize',14); %size

title('Plot Showing how time spent on convolution differs with technique applied')

************************************************************************************************************************

Section 3

format LONGENG; %increased precision

[x,fs]=audioread('africa-toto.wav');

x=x'; % Column vector transposed

yy37=[1:37]; % 37 place line vector created for further storage

h=ones(1,18); % this line vector will accept given values

h(1)=-0.0000000000000020464110886333966;

h(2)=0.020185108207322531;

h(3)=-0.0000000000000032166461686436967;

h(4)=0.0063932717248746463;

h(5)=-0.0000000000000042068450824985665;

h(6)=-0.030584021511458139;

h(7)=-0.0000000000000037927619003410752;

h(8)=0.0092608976386982338;

h(9)=-0.0000000000000034686968012612998;

h(10)=0.055319499353126252;

h(11)=-0.0000000000000029165858917179788;

h(12)=-0.062431158774528053;

h(13)=-0.0000000000000030126051803342088;

h(14)=-0.079105057829546827;

h(15)=-0.0000000000000030966220578734095;

h(16)=0.3013776867026185;

h(17)=-0.0000000000000028385702197172922;

h(18)=0.58901882620106349;

yy37(1)=0.0053712613864042745; %the value manually given because there is no y(0)

yy37(2:19)=h; %line vector copied to filter coefficients

for i=1:18 % for loop used for the rest of values.

yy37(19+i)=yy37(19-i);

end

% The lenght of x will be step by step increased (65 steps) and during

% each step both Linear and FFT willl be used for obtaining convolution.

% The mean time of each operation on total 3 will be stored for further

% discussion

M1_time=zeros(65,1); % time variable vector for obtaining mean time during each cycle from Linear

M2_time=zeros(65,1); % time variable vector for obtaining mean time during each cycle from FFT

for k=1:65 % Loop will be repeated 65 times, each time value of k will be incremented by +1 starting from 1.

x_new=x(1:100000*k); % During Each loop the lenght of x_new signal will be increased by 100000*k samples.

t1 = zeros(1,3); % Vector for storing time values

for n = 1:3 %Looping repeats 3 times

tic; % Timer started

x_c=conv(x_new,yy37); %Operation of convolution

t1(n)=toc; %During each loop relevant value of timer will be copied and timer will be reset

end

t2 = zeros(1,3); % Vector for storing time values

yy37Pad=[yy37 zeros(1,length(x_new)-1)]; %Zero Padding

xPad=[x_new zeros(1,length(yy37)-1)]; %Zero Padding

for n = 1:3 %Looping repeats 3 times

tic; % Timer started

x_c2=ifft(fft(xPad).*fft(yy37Pad)); % Obtaining inverse transform from fft

t2(n)=toc;

end

%Average value of time spent for operation obtained and stored in respective element of row vector.

M1_time(k)=mean(t1);

M2_time(k)=mean(t2);

end

figure(1)

plot(M1_time)

hold on

plot(M2_time)

xlabel('Number of elements, in 10^5')

ylabel('Time, sec')

legend ('Linear Conv','FFT')

Rik
on 11 Mar 2020

### Answers (2)

Rik
on 11 Mar 2020

Why would a textbook say ifft(fft()) is faster? That doens't make sense. If that was the case, Mathworks would have implemented conv a bit like this:

function out=conv(x,h)

out=ifft(fft(x).*fft(h));

end

The mere fact that they didn't should tell you the real conv function is faster than the one I put here.

##### 0 Comments

Honglei Chen
on 11 Mar 2020

Time is not the best way to compare the two approaches. Rather, the best approach to describe is the computation complexity, i.e., when the size of the signal increases, how does the time of computation increases accordingly. It is in this comparison that the FFt approach shows the advantage. The theory should be available in any standard DSP text book and here is a webpage for a summary

HTH

##### 1 Comment

Rik
on 11 Mar 2020

### See Also

### Categories

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!