Как суммировать части матрицы разных размеров, не используя для циклов?

Question

У меня относительно большая матрица NxN (N ~ 20000) и вектор Nx1, идентифицирующий индексы, которые должны быть сгруппированы вместе.

Я хочу суммировать части матрицы, которая в принципе может иметь разное количество элементов и несмежных элементов. Я быстро написал двойной цикл for, который работает правильно, но, конечно, он неэффективен. Профилировщик определил эти циклы как одно из узких мест в моем коде.

Я попытался найти умный метод векторизации для решения проблемы. Я исследовал функции arrayfun, cellfun и bsxfun и искал решения похожих проблем ... но пока не нашел окончательного решения.

Это тестовый код с двумя циклами for:

M=rand(10); % test matrix
idxM=[1 2 2 3 4 4 4 1 4 2]; % each element indicates to which group each row/column of M belongs
nT=size(M,1);
sumM=zeros(max(idxM),max(idxM));
for t1=1:nT
    for t2=1:nT
        sumM(t1,t2) = sum(sum(M(idxM==t1,idxM==t2)));
    end
end

Answer 1

Решение с использованием cumsum и diff.

[s,is] = sort(idxM);
sumM  = M(is,is);
idx = [diff(s)~=0 ,true];
CS = cumsum(sumM);
CS = cumsum(CS(idx,:),2);
n=sum(idx);
result = diff([zeros(n,1) diff([zeros(1,n); CS(:,idx)])],1,2);
sumM (:)=0;
sumM (s(idx),s(idx))=result;

Answer 2

Я бы хотел указать тем, кому интересен этот ответ, предоставленный на другом форуме

S=sparse(1:N,idxM,1); sumM=S.'*(M*S);

Кредиты (и полезное обсуждение):

https://www.mathworks.com/matlabcentral/answers/407634-how-to-sum-parts-of-a-matrix-of-different-sizes-without-using-for-loops

Answer 3

Вы можете использовать accumarray следующим образом:

nT = size(M,1); % or nT = max(idxM)
ind = bsxfun(@plus, idxM(:), (idxM(:).'-1)*nT); % create linear indices for grouping
sumM = accumarray(ind(:), M(:), [nT^2 1]); % compute sum of each group
sumM = reshape(sumM, [nT nT]); % reshape obtain the final result