Efficient multiplication by large structured matrix of ones and zeros
2 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
I am trying to do a relatively simple operation, with a prototypical example:
N = 20;
B = de2bi((1:2^N)-1,N);
c = rand(2^N,1);
result = sum(B.*c,1);
Now this works well, and seems relatively efficient, but when N grows larger, the B matrix will be 2^N x N, which gets prohibitive quite fast. I could make it a sparse matrix which would save half the memory, but that just buys one extra N before memory constraints are reached again. I'm wondering if there are any clever and efficient ways to perform this operation without necessarily saving the B matrix given that it is so structured. Thanks!
0 Commenti
Risposta accettata
Matt J
il 14 Ott 2022
Modificato: Matt J
il 14 Ott 2022
It may seem counter-intuitive that this version is faster than the versions in my earlier comment, since it does twice as much summation. I imagine it's because it's better multi-threaded and requires less memory allocation.
N = 24; % not so small
c = rand(2^N,1);
tic;
chat = reshape(c,repmat(2,1,N));
e=1:N;
clear result2
for i = 1:N
tmp=sum(chat,setdiff(e,i));
result2(N+1-i) = tmp(2); %#ok<SAGROW>
end
toc
2 Commenti
John D'Errico
il 15 Ott 2022
Nice. The funny thing is, when I first looked at this question, I was thinking that it would not be possible to see a gain over the brute force matrix multiply. My gut was wrong of course.
Più risposte (1)
John D'Errico
il 14 Ott 2022
Modificato: John D'Errico
il 14 Ott 2022
Are there more efficient ways to do this? Well, perhaps, arguably so. Why you want to do it, is I supose your problem.
THINK about what you are doing here. What does that multiply do? It forms linear combinations of the vector C, with the bits of the numbers 0:2^N-1.
For example...
N = 5; % small, so we can see what happens.
B = de2bi((1:2^N)-1,N);
c = rand(2^N,1);
format long g
result = sum(B.*c,1)
Now using a different code, can we reproduce that? One idea is to convert c into a multi-dimensional array. Then sum only the appropriate elements, permuting the elements of that array.
chat = reshape(c,repmat(2,1,N));
result2 = zeros(1,N);
for i = 1:N
chati = reshape(permute(chat,[i,setdiff(1:N,i)]),2,[]);
result2(i) = sum(chati(2,:));
end
result2
So I never computed B. I did a fair amount of work to perform the computations though. Is there a gain when N is large? It may start to gain when N grows moderately large.
1 Commento
Matt J
il 14 Ott 2022
Modificato: Matt J
il 14 Ott 2022
No need to permute:
N = 24; % not so small
c = rand(2^N,1);
tic
B = de2bi((1:2^N)-1,N);
result = sum(B.*c,1);
toc
tic;
chat = reshape(c,repmat(2,1,N));
result2 = zeros(1,N);
for i = 1:N
chati = reshape(permute(chat,[i,setdiff(1:N,i)]),2,[]);
result2(i) = sum(chati(2,:));
end
toc
tic;
chat = reshape(c,repmat(2,1,N));
inds0=repmat({':'},1,N);
result2 = zeros(1,N);
for i = 1:N
inds=inds0;
inds{i}=2;
result2(i) = sum(chat(inds{:}),'all');
end
toc
Vedere anche
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!