Fast multiplication: binary matrix with double matrix

13 views (last 30 days)
Hello everyone,
I am trying to speed up my Matlab code at the moment. The most time consuming part of the code is the multiplication of two matrices A*B, where A is binary (only 0 or 1 entries) and B is a double matrix.
The size of the matrices isn't that large, it's only time consuming because its in the inner loop of some iteration and thus is performed 100k upto a million times. (The matrix B is changing in each iteration, but A stays the same.) So each bit of performance speed-up could help me out here.
At the moment, I am just converting A from binary to double and use the standard matrix multiplication A*B. However, I wonder if there is a faster way to do it. since A is binary, A*B is not a 'real multiplication' but just an addition of some elements of B (defined by the non-zero pattern of A). Anyone has a clue how to do so? And neither A nor B are sparse, if that is important.
  5 Comments
Florian
Florian on 6 Aug 2019
A and B don't need to be square, but size(A,2)==size(B,1). And yes, the loop is like
for k=1:numIterations
X = A*B;
%some other calculations on X
B = B+X;
end
A does not have replicated rows.
The structure in the mex file would be the same, but instead of having a multiplication inside the loop (element of A times element of B), there would be an if statement (if element of A is unequal 0) and an addition (add element of B to the result). The if statement could be moved to the outer loop I guess. So, I am not sure if that could save some time alltogether. But if there is no better approach, I might try to write this.
Bruno Luong
Bruno Luong on 6 Aug 2019
I doubt you can beat MATLAB matrix multiplication (highly optimized) with MEX file. The time depends on little on the number of operations, but memory copying, etc ... count.

Sign in to comment.

Answers (2)

Walter Roberson
Walter Roberson on 6 Aug 2019
It turns out to be faster to leave A as logical when you do the matrix multiplication.
Using logical indexing, or doing find() and adding only those elements, is much slower unless the occupancy fraction drops to below 10% as a rough estimate.
  4 Comments
Florian
Florian on 6 Aug 2019
Edited: Florian on 6 Aug 2019
I think you got my question wrong. I want to compute the product A*B. However, because A is binary, this product can be interpreted as "the addition of elements of B". My question was, if this fact can be used somehow to speed up A*B.
Also, how does A.*B sum up elements of B? Isn't it just setting some of the elements to zero?.
Walter Roberson
Walter Roberson on 6 Aug 2019
Ah, I guess I must have mis-interpreted the question.

Sign in to comment.


Bruno Luong
Bruno Luong on 6 Aug 2019
Edited: Bruno Luong on 6 Aug 2019
Here is two ways, it won't be faster than A*B as other has warned you
n = 512;
A = sprand(n,n,0.1) > 0 ;
B = rand(n,n);
m = size(A,1);
p = size(B,2);
[i,j] = find(A);
C = zeros(m,p);
tic
for k = 1:p
C(:,k) = accumarray(i,reshape(B(j,k),[],1),[m,1]);
end
toc
m = size(A,1);
p = size(B,2);
[i,j] = find(A);
k = 1:p;
[I,K] = ndgrid(i,k);
tic
C = accumarray([I(:),K(:)],reshape(B(j,k),[],1));
toc
tic
C = A*B;
toc

Products


Release

R2018b

Community Treasure Hunt

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

Start Hunting!