File Exchange

image thumbnail

Sparse matrix convolution

version 1.0 (1.4 KB) by

Convolution of sparse matrices

1 Download

Updated

View License

Same as CONV2 but suitable when using with sparse matrices

Comments and Ratings (11)

"The code by itself is clear, ..."
That is such a ridiculous comment that I needed to highlight it.

"I challenge you to be able to implement the same functionality that is faster than mine."
That is easy. Just use conv2. See the third example of my compare script from my 8 June 2017 comment

Bruno Luong

Bruno Luong (view profile)

Any serious software engineers would take a look at CONV2 and know what it does and test it, since the CONV2 help is detailed and well explained. The calculation inside the code is totally trivial to me that one does not need an explicit comment. The code by itself is clear, no need 1000 words. Those are not able to understand or do not make an effort to do so should stay away from coding IMO.

Apparently you do not understand rudimentary software engineering. Any code but especially FEX code should be written and commented so that future users (including you) can understand, test, and modify it for other purposes. The body of your code has absolutely no comments. You do not even explain the 'shape' variable in your header. Use of single letter variable names went out in the 1950's. I think 2 stars is generous.

Bruno Luong

Bruno Luong (view profile)

Indeed, you are free to do reverse engineering.

If you want to learn, then ask question in the forum, the right place to do it. The codes I post in FEX is NOT for educational purpose whereas you think it is FEX "spirit", it is mainly for usage for whoever need it.

Try to run again your benchmark code with nrows and ncols = 10000 and see the result.

If you do not see the advantage in your test matrix, then your matrix is not sparse enought to take advantage of the function, just like the case many other TMW functions of MTIMES, MDIVIDED.

I challenge you to be able to implement the same functionality that is faster than mine.

You have also the right to rate my FEX 2 stars. Personally *I* know what this 2 stars mean.

Apparently Mr. Luong does not understand either the spirit of the FEX or the letter of the license that Mathworks requires FEX authors to provide. I am fully within my rights to 'reverse engineer' the code and it is the spirit of FEX to provide an environment where participants can learn from each other.

In this spirit, I wrote some code to compare conv2 and sconv2:

%% compare sconv2 to conv2
nrows = 1000; % number rows
ncols = 1000; % number columns
rng('default'); % set seed for reproducible results
for nsparse = [100 1000 5000]
% create sparse matrices with random values at random points
m1 = sparse(ceil(nrows*rand(nsparse,1)),ceil(ncols*rand(nsparse,1)),rand(nsparse,1), ...
nrows,ncols);
m2 = sparse(ceil(nrows*rand(nsparse,1)),ceil(ncols*rand(nsparse,1)),rand(nsparse,1), ...
nrows,ncols);
% compare convolve times
tic
c1 = conv2(full(m1),full(m2));
fprintf('nsparse %d conv2 time %g\n',nsparse,toc);
tic
c2 = sconv2(m1,m2);
fprintf('nsparse %d sconv2 time %g\n',nsparse,toc);
fprintf('\n');
end
Here are the results:
nsparse 100 conv2 time 0.0617252
nsparse 100 sconv2 time 0.00394388

nsparse 1000 conv2 time 0.180278
nsparse 1000 sconv2 time 0.137812

nsparse 5000 conv2 time 0.775147
nsparse 5000 sconv2 time 3.29617

Comments:
1. Note that m1 and m2 are 1000x1000 for all cases and in all cases the fraction of non-zero points is very small.
2. For 100 non-zero points sconv2 is substantially faster than conv2 but both times are so small that they are negligible.
3. For 1000 points both functions' times are about the same.
4. For 5000 points, conv2 is substantially faster than sconv2.
My conclusion is that sconv2 is not needed. Apparently conv2 tests for sparse matrices and handles these cases more gracefully than sconv2.
My 2 star rating of sconv2 stands.

Bruno Luong

Bruno Luong (view profile)

The FEX author does not have obligation to provide the "algorithm", nor make it easy to other for reverse engineering, and I'll not do it for you in this particular case.

The reason I downgraded is that you do not explain the algorithm and there are no comments in your code making it very hard to read.

Can you provide an explanation of the algorithm or a reference to where it is explained?

Bruno Luong

Bruno Luong (view profile)

To Alvarez: it simply works like CONV2, nothing complicated to explain. But I'll do for you:

full(sconv2(A,B))

will be equal to conv2(A,B), excepted that sconv2(A,B) can accept sparse matrices as inputs and always returns sparse matrix as output.

Why do you rate 2 stars if you don't understand how it works?

OK, options are explained in conv2 documentation.

'full' Returns the full two-dimensional convolution (default).

'same' Returns the central part of the convolution of the same size as A.

'valid' Returns only those parts of the convolution that are computed without the zero-padded edges. Using this option, size(C) = max([ma-max(0,mb-1),na-max(0,nb-1)],0).

But how does code work?

MATLAB Release
MATLAB 8.1 (R2013a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video