Efficient multiplication by large structured matrix of ones and zeros

Question

Adam Shaw 2022-10-14

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1826493-efficient-multiplication-by-large-structured-matrix-of-ones-and-zeros

编辑： Adam Shaw 2022-10-15

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Matt J 2022-10-14

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1826493-efficient-multiplication-by-large-structured-matrix-of-ones-and-zeros#answer_1075128

编辑：Matt J 2022-10-14

在 MATLAB Online 中打开

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
Elapsed time is 0.260331 seconds.

2 个评论
显示无隐藏无

John D'Errico 2022-10-15

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.

Adam Shaw 2022-10-15

编辑：Adam Shaw 2022-10-15

Fantastic solution, thanks! Note that I think you just need result2(i) = tmp(2) - it seems flipped from the brute force matrix multiplication to me.

请先登录，再进行评论。

Answer 2

John D'Errico 2022-10-14

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1826493-efficient-multiplication-by-large-structured-matrix-of-ones-and-zeros#answer_1075068

编辑：John D'Errico 2022-10-14

在 MATLAB Online 中打开

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)
result = 1×5
          9.65859767786247           7.1472229443395          9.89441940297802          8.23946581063777          8.39175263434243

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
result2 = 1×5
          9.65859767786247           7.1472229443395          9.89441940297802          8.23946581063777          8.39175263434243

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Matt J 2022-10-14

编辑：Matt J 2022-10-14

在 MATLAB Online 中打开

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
Elapsed time is 8.992176 seconds.
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
Elapsed time is 2.891254 seconds.
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
Elapsed time is 1.551022 seconds.