runtime of sparse matrix components allocation

Question

reza aghaee 2020-5-2

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/522498-runtime-of-sparse-matrix-components-allocation

回答： Deepak 2024-11-7，9:35

Nobs = 20000;
K = 20;
tic
H = sparse([],[],[],Nobs,Nobs,4*K*Nobs);
for j = 1 : Nobs    
    jj = randi(Nobs,1,K);
    H(j,jj) = 1;
    H(jj,j) = 1;    
end
toc

Hi,

I have a problem with sparse matrix components allocation. Why does the allocation of matrix components slow down as the loop moves forward (with increase of j)?

Run time of the above code with n = 20000 is 6 s., but with n = 60000 (tripled), run time becomes 90s. (15 times greater).

How can i fix this problem?

Thanks

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

请先登录，再进行评论。

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

Answer 1

Deepak 2024-11-7，9:35

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/522498-runtime-of-sparse-matrix-components-allocation#answer_1542340

在 MATLAB Online 中打开

Hi @reza aghaee,

The performance slowdown you are observing is due to the way MATLAB handles sparse matrix allocation. Although you have pre-allocated space for the sparse matrix H using

H = sparse([],[],[],Nobs,Nobs,4*K*Nobs);

the dynamic insertion of elements within the loop can still lead to inefficiencies.

Each time you update the matrix with H(j,jj) = 1; and H(jj,j) = 1;, MATLAB may need to reallocate memory or rearrange the internal structure of the sparse matrix, especially as the matrix fills up.

To address this issue and improve performance, we can follow the following strategies:

Precompute Indices and Values: Instead of updating the matrix within the loop, precompute all indices and values and then create the sparse matrix in one go. This approach minimizes dynamic memory allocation.
Use Vectors for Indices: Collect all row indices, column indices, and values in vectors, and construct the sparse matrix after the loop.

Here is the updated MATLAB code with the required changes:

Nobs = 60000; 
K = 20; 
tic 
% Preallocate vectors for indices and values 
row_indices = zeros(2 * K * Nobs, 1); 
col_indices = zeros(2 * K * Nobs, 1); 
values = ones(2 * K * Nobs, 1); 
index = 1; 
for j = 1:Nobs 
    jj = randi(Nobs, 1, K); 
    
    % Store indices and values for both H(j,jj) and H(jj,j) 
    row_indices(index:index+K-1) = j; 
    col_indices(index:index+K-1) = jj; 
    index = index + K; 
    
    row_indices(index:index+K-1) = jj; 
    col_indices(index:index+K-1) = j; 
    index = index + K; 
end 
% Create the sparse matrix in one step 
H = sparse(row_indices, col_indices, values, Nobs, Nobs); 
Toc 
Elapsed time is 0.444608 seconds. 