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

조회 수: 50 (최근 30일)
Alim Huseynov 2017년 12월 1일
댓글: Rik 2020년 3월 11일
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이전 댓글 2개 표시이전 댓글 2개 숨기기
Alim Huseynov 2020년 3월 11일
편집: Rik 2020년 3월 11일
Section 1. (for Problem 1)
format LONGENG; %increased precision
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=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
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=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
for n = 1:3 %Looping repeats 3 times
tic; % Timer started
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 2020년 3월 11일
Just a note: format LONGENG will not increase calculation precision, it will only affect how values are shown in the command window.

댓글을 달려면 로그인하십시오.

### 답변 (2개)

Rik 2020년 3월 11일
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이전 댓글 -2개 표시이전 댓글 -2개 숨기기

댓글을 달려면 로그인하십시오.

Honglei Chen 2020년 3월 11일
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이전 댓글 -1개 표시이전 댓글 -1개 숨기기
Rik 2020년 3월 11일
I would expect the implementation in Matlab to be a black box: it is not relevant if internally there is an FFT or direct approach, as long as it gives the correct output. That is true in general for internal functions. Your comment about computational complexity still holds, but I expect the Mathworks employees that engineered the conv function to know about this.

댓글을 달려면 로그인하십시오.

### 카테고리

Help CenterFile Exchange에서 Fourier Analysis and Filtering에 대해 자세히 알아보기

### Community Treasure Hunt

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

Start Hunting!

Translated by