Fast multiplication: binary matrix with double matrix

4 次查看（过去 30 天）
Florian
Florian 2019-8-6
评论： Bruno Luong 2019-8-6
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 个评论
显示 3更早的评论
Florian
Florian 2019-8-6
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 2019-8-6
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

Walter Roberson
Walter Roberson 2019-8-6
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 个评论
显示 2更早的评论
Florian
Florian 2019-8-6
编辑：Florian 2019-8-6
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?.

请先登录，再进行评论。

Bruno Luong
Bruno Luong 2019-8-6
编辑：Bruno Luong 2019-8-6
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

类别

在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息

标签

产品


版本

R2018b

Community Treasure Hunt

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

Start Hunting!

Translated by