Time 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 (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 problems?

With spacial thanks

Answer 1

[David Goodmanson]

Hi reza,

with sparse matrices you want to build up a set of indices to use in the first two inputs, in order to make a single call to sparse if possible. That process is pretty fast. Updating a large sparse matrix is much, much slower.

Nobs = 20000;
K = 20;

tic
ind1 = repmat(1:Nobs,K,1);
ind1 = ind1(:);                % indices 1 to Nobs, each repeated K times
ind2 = randi(Nobs,Nobs*K,1);   % full set of random indices
ind12 = [ind1 ind2];
ind = [ind12; fliplr(ind12)];  % fliplr produces the transposed element 
H1 = sparse(ind(:,1),ind(:,2),1);
toc
Elapsed time is 0.120881 seconds.

[reza aghaee]

Thank you

The problem was solved with your answer

Answer 2

[James Tursa]

Every time you add even one element to a sparse matrix, it has to copy data ... perhaps all of the current data ... to make room for your new element. And if the current allocated sizes aren't enough, it has to allocate new memory as well. The bulk of your timing (often 99% of it) is being spent in repeated data copying (many, many times for the same elements) instead of the actual element assignment.

With sparse matrices, you should gather all of the indexing and data values up front, and build it only once to avoid this data copying and extra allocations.

[reza aghaee]

Thanks for your guidance