Sparse matrix is very slow in loop, how to speed it up in Matlab

Question

I have a huge matrix(584064x5369468) and I have to use sparse matrix in Matlab, but in my calculation it is very slow to assign a value to a sparse matrix. I cannot wait to finish it, what should I do.

cgm=sparse(584064,5369468);
[Xcp, Ycp, Zcp] = ndgrid(-[1:336],-[1:45],-[1:336]);
% dp my data which is loaded

for sg=1:335 
    for tg=1:44
        for rg=1:335
            % ii is a vector i.e the size of ii = 309x1
            fprintf('Constructing patch: %i %i %i',sg,tg,rg)
            ii=find(abs((Xcp(sg,tg,rg))<=abs(dp(:,1)))&abs((dp(:,1))<abs(Xcp(sg+1,tg,rg)))&(abs(Ycp(sg,tg,rg))<=abs(dp(:,2)))& (abs(dp(:,2))<abs(Ycp(sg,tg+1,rg)))& (abs(Zcp(sg,tg,rg))<=abs(dp(:,3)))&(abs(dp(:,3))<abs(Zcp(sg,tg,rg+1))));

              % jj is another vector i.e the size of jj = 64*1
              %the ii size is changing every time but the size of jj is always 64. ii is non-zero values and can be between 1 and 584064 .
              % c is my matrix after calculation i.e c = 309x64
             cgm(ii,jj)=c;
        end
     end
end

For the first internal loop it goes very fast but it become slower and slower drastically.

I know that assigning value to sparse matrix means repack everything and it is very slow, but how to repack it less in my code?

Thanks

I don't understand what you're doing. You're not using the loop variables and I have no idea how that assignment is working with ii and jj being different sizes. — beaker
@beaker i use loop variables to make ii and jj values. should I update my code? — Ehsan
I'm still very confused about your calculations, but you should be accumulating the rows, columns and values for each non-zero and using S = sparse(i, j, v) as shown here (or maybe S = sparse(i, j, v, m, n)). — beaker
@Ehsan - Those negatives added to ndgrid were not there before. Either way, thanks. — rayryeng
@Ehsan - i, j, and v are all N x 1 vectors and populate your sparse matrix C such that C(i(k), j(k)) = v(k) for k = 1, 2, ... , N. All other values would be zero. I would also recommend you override the size and do C = sparse(i, j, v, 584064,5369468); so that you're sure you get the desired size. — rayryeng

Yair Altman Yair Altman · Accepted Answer · 2015-06-25T07:00:17

As @beaker mentioned above, and as I explain in my Accelerating Matlab Performance book, using the sparse or spdiags functions is much faster than using indexed assignments as in your code.

The reason is that any such assignment results in a rebuilding of the sparse data's internal representation, which is increasingly slower the more data elements need to be rearranged.

Instead, you should accumulate the data indices (ii and jj) as well as the assigned data (c) into three separate arrays within your loops, and then, outside the loop use a single call to sparse(ii,jj,c) to update the matrix in a single go. This will be much faster.

See pages 137-140 in my book for additional details and suggestions related to sparse data.

Sparse matrix is very slow in loop, how to speed it up in Matlab

1 Answers