Fast multiplication: binary matrix with double matrix
14 ビュー (過去 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!