4

i'm running the following code, where M is a ~200,000 by ~200,000 sparse matrix and points is ~200,000 by 2 matrix

inds=sub2ind(size(M),points(:,1),points(:,2));
M(inds)=M(inds)+1;

the problem is that the second line takes very long to run (15-90 seconds). the operation takes longer depending on how many of the indices in inds are 'new' (i.e. that don't already have a value in the sparse matrix)

is there a more efficient way to do this?

1 Answer 1

4

Here's an idea:

M = M + sparse(points(:,1),points(:,2),1,size(M,1),size(M,2),size(points,1));

Just so you know,

S = sparse(i,j,s,m,n,nzmax) uses vectors i, j, and s to generate an m-by-n sparse matrix such that S(i(k),j(k)) = s(k), with space allocated for nzmax nonzeros. Vectors i, j, and s are all the same length. Any elements of s that are zero are ignored, along with the corresponding values of i and j. Any elements of s that have duplicate values of i and j are added together.

For the curious:

M = sprand(200000,200000,1e-6);
points = [randperm(200000) ; randperm(200000)]'; %'//Initialization over
Mo = M;
tic; 
inds=sub2ind(size(Mo),points(:,1),points(:,2));
Mo(inds) = Mo(inds)+1;
toc
tic; 
M = M + sparse(points(:,1),points(:,2),1,size(M,1),size(M,2),size(points,1));
toc
2
  • 1
    @pseudoDust, how faster did it become? Commented Oct 8, 2012 at 14:09
  • @Andrey: You can test it for yourself with the demo code I added
    – Jacob
    Commented Oct 8, 2012 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.