Fast multiplication: binary matrix with double matrix
2 次查看(过去 30 天)
显示 更早的评论
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 个评论
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
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 个评论
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
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!