Help on zero padding and understanding of the following example?

2 views (last 30 days)
blues on 1 Mar 2021
Commented: Allen on 1 Mar 2021
To understand the concept and impact of zero padding on computation time, I have created an example below and run the program and note the time taken to complete the program. Using the following program I assume, I will get a lowest time using 3 (with zero padding to array1, see below), but this was not the case. I got the different result than my assumption! Where did I make the mistake? Could you help me?
% Create an example of zero-padding
close all; clear; clc; workspace
array1 = rand(41,41,41);
array2 = ones(256,256,199);
%% 1. direct convolution
tic
A = convn(array1, array2);
toc
%% 2. without zero padding: FFT method
tic
B = fftn(array1);
C = fftn(array2);
D = ifftn(convn(B, C));
toc
%% 3. with zero padding to array1
% insert array1 in the middle of zeros matrix
tic
F = fftn(array2);
% Now, E and F are of same size
G = ifftn(convn(E, F));
toc
Elapsed time is 36.725312 seconds.
Elapsed time is 7.637434 seconds.
Elapsed time is 197.981833 seconds. ....>>>> If the zero padding was right then this time should be lower than above two, right?

KALYAN ACHARJYA on 1 Mar 2021
Edited: KALYAN ACHARJYA on 1 Mar 2021
"If the zero padding was right then this time should be lower than above two, right?"
How?
The only difference between section 2 and 3 are B and E, remain code are exactly same (Within tic toc)
>> whos B
Name Size Bytes Class Attributes
B 41x41x41 1102736 double complex
>> whos E
Name Size Bytes Class Attributes
E 256x256x199 208666624 double complex
E here
Both section (2 and 3) are performing the same operation, except for one variable in segnment 3, which has larger data size (E) as compare to it's counterpart (B) in section 2, therefore expecting higher execution time than section 2
Hello experts and others members, Am I missing something here? Or this is a simple case, as I have mentioned.
blues on 1 Mar 2021
I may have a wrong belief, but as I understand, the FFT generally requires the zero padding to attain maximum computational efficiency. If the elapsed time in part 3 is greater then time taken in part 2 then what is its advantage? Could someone enlighten me please?
Allen on 1 Mar 2021
Not sure what the output from these functions is supposed to look like in terms of array size, but the results from method 2 and 3 both produce a resulting array whos size is the sum of the size of each input array minus one. Since the size of E>B, this also means that size of G>D and hence the longer computational time.
>> size(B)+size(C)-1
ans =
296 296 239
>> size(D)
ans =
296 296 239
>> size(E)+size(F)-1
ans =
511 511 397
>> size(G)
ans =
511 511 397