Counting average on huge matrix with conditional

问题:

The following MATLAB code runs forever on 10^5 square matrix A. However, it runs for a few seconds on 10^3 square matrix. Is there any way to speed it up?

function [meanNV]=calcMeanNV_k(A,V,d)
%A: input matrix (n x n)
%V: eigenvectors of k-th largest eigenvalues (n x 1)
%d: degrees of each node (n x 1)
%meanNV: mean of neighbors vectors (n x 1)
m=size(A,2);
meanNV=zeros(113336);
 for i=1:m
     sumNode = 0;
     for j=1:m
        if A(i,j)==1
            sumNode=sumNode+V(j);
        end
     end
    [meanNV(i)]=sumNode/d(i); 
 end

回答1:

Simply put, for each row in A, you are determining the locations that are non-zero and using these indices to sum over the corresponding locations in V and dividing by the corresponding entry in d.

First use find to determine the non-zero row and column locations, then group all of the column locations by their common rows using accumarray and the function to apply on accumarray would simply sum over all indices once you index into V.

Something like this could work:

function [meanNV]=calcMeanNV_k1(A,V,d)
%A: input matrix (n x n)
%V: eigenvectors of k-th largest eigenvalues (n x 1)
%d: degrees of each node (n x 1)
%meanNV: mean of neighbors vectors (n x 1)

m=size(A,2);
[row,col] = find(A); % Find non-zero entries in A
meanNV = accumarray(row, col, [m 1], @(x) sum(V(x))) ./ d; % Compute desired result

end

回答2:

This what works:

function [meanNV]=calcMeanNV_k1(A,V,d)
%A: input matrix (n x n)
%V: eigenvectors of k-th largest eigenvalues (n x 1)
%d: degrees of each node (n x 1)
%meanNV: mean of neighbors vectors (n x 1)
tic
m=size(A,2);
meanNV=zeros(m,1);
idx = A == 1;
for k = 1:m
   meanNV = sum(V(idx(k,:)));
end
meanNV = meanNV./d;
toc