runtime of sparse matrix components allocation

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

Answer 1

[Deepak]

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:

1. 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.
2. 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. 

Please find attached the documentation of functions used for reference:

Array indexing: www.mathworks.com/help/matlab/math/array-indexing.html

Sparse: www.mathworks.com/help/matlab/ref/sparse.html

I hope this helps in resolving the issue.