Much slower valid convolution using complementary size of kernels.

I am using the valid convolution using convn( T, a, 'valid').

I have run the code below:

T = randn(384,384,8);
a = randn(5,5,8);
b = randn(380,380,1);

tic; convn(T,a,'valid'); toc
tic; convn(T,b,'valid'); toc

The reuslt in my computer is

Elapsed time is 0.002837 seconds.
Elapsed time is 0.016301 seconds.

Thus the the latter is much slower compared to fomer one.

However, in terms of flops, or only in terms of multiplications

convn(T,a,'valid')

takes 5*5*8*(384-5+1)*(384-5+1)*(8-8+1) = 28880000 multiplications

convn(T,b,'valid')

also takes 380*380*1*(384-380+1)*(384-380+1)*(8-1+1) = 28880000 multiplications

So why are the two computing time so different?

And is there some ways to implement the convn(T,b,'valid') much faster?

[Bruno Luong]

"So why are the two computing time so different?"

Just a guess but convn(T,a,'valid') possible more suitable to be parallelize since the result is (380 x 380) and each can be computed independently.

Whereas convn(T,a,'valid') is harder.

[Shen Zhao]

I understand your first point, this seems to infer that the difference between the two convolution using GPU will be more severe.

However, in which perspective convn(T,a,'valid') is harder? FLOPS? or hardware implementation?

[Bruno Luong]

No not FLOPS. As you said the FLOPS are more or less indentical.

Answer 1

[Bjorn Gustavsson]

No, n-dimensional fourier-transforms, multiplication of the Fourier-transforms of 5-5-8 a with T will be a fair bit faster than the multiplication of the 380-by-380-by-1 b with T.

HTH

Answer 2

[Roshan Hingnekar]

T and 'a' are 3 dimensional where as 'b' is 2 dimensional, convolution of 3-dimensional with 2-dimensional will be slower than a 3-dimensional with a 3-dimensional.

refer to the below links for further insight on randn and convn functions.

https://www.mathworks.com/help/matlab/ref/randn.html

https://www.mathworks.com/help/matlab/ref/convn.html?searchHighlight=convn&s_tid=srchtitle

[Shen Zhao]

I read the corredponding webpages, could you explain more on why the same dimensional convolution will be faster?

Answer 3

[Bruno Luong]

I would suggest to do specific conv with MEX programing.

Not sure the chance to beat MATLAB though.

[Shen Zhao]

We once tried to write some C++ code to compete with matlab convn especially for 'valid' convolution, we found it really hard to beat Matalb convn. The matlab convn is really well-optimized.