Optimize filling of sparse matrix: "This sparse indexing expression is likely to be slow."

Question

David 2017-7-18

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/349261-optimize-filling-of-sparse-matrix-this-sparse-indexing-expression-is-likely-to-be-slow

评论： Monisha S R 2018-11-22

采纳的回答： Steven Lord

在 MATLAB Online 中打开

Hi,

I have a sparse matrix for which I'm replacing certain values in a foor-loop structure. It all goes on the lines of

A = sparse(n,n);
for i = 1:size(Im,1);
  for j = 1:size(Im,2);
      for k = 1:size(Im,3);
        row = ind(i,j,k);
        if(Labels(i,j,k) == -1)
           continue 
        elseif(Labels(i,j,k) == 1) || (Labels(i,j,k) == 2)
            A(row,row) = 1;
            continue
        end
          [sx, sx_value, sy, sy_value, sz, sz_value] = myFunction(Labels,i,j,k);
          A(row,ind(i+sx,j,k)) = A(row,ind(i+sx,j,k)) + sx_value;
          A(row,ind(i,j+sy,k)) = A(row,ind(i,j+sy,k)) + sy_value;
          A(row,ind(i,j,k+sz)) = A(row,ind(i,j,k+sz)) + sz_value;
          end
        end
    end
  end

Basically what I have is a 2D matrix Im and a (large) number n over which I create a sparse matrix A. I then loop over all dimensions (perhaps not optimal, I know) and for certain situations (that is certain rows of n) I call a function, and set values of A with the output of that function, on the lines of

A(i,j) = myValue;

For large values of n (e.g. 500, 1000, etc.) the code is very slow. I ran some profiling and the specific lines where I fill values in A indicates as

This sparse indexing expression is likely to be slow.

On the help I saw some suggestions of not doing this to sparse matrices but rather initiating e.g. A = zeros(...) and 'sparsifying' it in the end. The problem when n is large though, is that I cannot allocate enough memory for A = zeros(...).

Anyone got any suggestions of how to improve the code? Any help would be really great!

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Steven Lord 2017-7-18

3
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/349261-optimize-filling-of-sparse-matrix-this-sparse-indexing-expression-is-likely-to-be-slow#answer_274629

In this case I would construct the i, j, and v vectors containing row and column indices and values respectively inside the loop. Call sparse once at the end to turn those vectors into the sparse matrix. See the "Accumulate Values into Sparse Matrix" example on the documentation page for the sparse function for a demonstration of this technique.

4 个评论
显示 2更早的评论隐藏 2更早的评论

David 2017-7-19

在 MATLAB Online 中打开

Just finished some tests. Both suggestions does improve the code, but it seems like Steven's initial thought gave the fastest speed-up (for the matrix sizes I am working with). For completeness a code example is below:

I = ones(6*n, 1); J = ones(6*n, 1); V = zeros(6*n, 1); 
iter = 1;
for i = 1:size(Im,1);
  for j = 1:size(Im,2);
      for k = 1:size(Im,3);
        row = ind(i,j,k);
        if(Labels(i,j,k) == exterior)
           continue 
        elseif(Labels(i,j,k) == inlet) || (Labels(i,j,k) == walls)
            I(iter) = row; J(iter) = row; V(iter) = 1; % Set pos. and value
            dirichlet(row) = 1; 
            iter = iter+1;
            continue
        end
        [sx, sx_value, sy, sy_value, sz, sz_value] = get_Ablock_stencil(Labels,i,j,k);
        % Set x-direction pos (I,J) and values (V)
        I(iter:iter+length(sx)-1) = row*ones(length(sx),1); 
        J(iter:iter+length(sx)-1) = ind(i+sx, j, k);
        V(iter:iter+length(sx)-1) = (sx_value./(PixDim(1)^2))';
        iter = iter+length(sx);
        % Set y-direction pos (I,J) and values (V)
        I(iter:iter+length(sy)-1) = row*ones(length(sy),1);
        J(iter:iter+length(sy)-1) = ind(i, j+sy, k)';
        V(iter:iter+length(sy)-1) = (sy_value./(PixDim(2)^2))';
        iter = iter+length(sy);
        if(image_is_3D)
            % Set z-direction pos (I,J) and values (V)
            I(iter:iter+length(sz)-1) = row*ones(length(sz),1);
            J(iter:iter+length(sz)-1) = ind(i, j, k+sz)';
            V(iter:iter+length(sz)-1) = (sz_value./(PixDim(3)^2))';
            iter = iter+length(sz);
        end
      end
  end
end
% Generate sparse matrix at the end
A = sparse(I,J,V);

For n ~ 500-1000 I had a speed-up of almost 80%! Another nice feature (I realized) is that if I,J is ever repeated in the input, sparse simply adds up V (which is exactly what I wanted). For completeness, doing spalloc(n,n,3*n) (or similar) gave ~20% speed-up in this case.

Note (for whoever reads this): initializing with 6*n is an arbitrary choice, based on a-priori info about A.

Again: thanks for all input.

Monisha S R 2018-11-22

@David Do you use spalloc before using sparse to construct the matrix?

请先登录，再进行评论。

Optimize filling of sparse matrix: "This sparse indexing expression is likely to be slow."

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

4 个评论
显示 2更早的评论隐藏 2更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

Optimize filling of sparse matrix: "This sparse indexing expression is likely to be slow."

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

4 个评论 显示 2更早的评论隐藏 2更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

4 个评论
显示 2更早的评论隐藏 2更早的评论