Find minimum non-zero entry in sparse matrix

Alec Jacobson

April 04, 2012

weblog/

Using a sparse matrix to store a weighted adjacency matrix, I found myself trying to grad the minimal non-zero entry per row. This is a little tricky since taking min will just give the first zero (and obviously taking max of the inverse also returns 0). Let your sparse matrix be:

A = sprand(10,10,0.5)-sprand(10,10,0.1);

This site proposes filling the zero entries with inf.

A(~A) = inf;
[mA,mI] = min(A);

But this turns our sparse matrix into a dense one. As A gets big this becomes a disaster.

[sA,sI] = sort(A,'descend');
[I,J,V] = find(sA);
msI = max(sparse(I,J,I));
mA = sA(sub2ind(size(A),msI,1:size(A,1)));
mI = sI(sub2ind(size(A),msI,1:size(A,1)));

Now, try this for 10000 by 10000 A with an average of 6 non-zeros per column. This replace with infs method takes crashed my matlab. So now try this for a 2500 by 2500 A with an average of 6 non-zeros per row. The replace with infs method takes 40.5 seconds, first converting the matrix to full format then replacing with infs does a lot better at 0.08 seconds, but the truly sparse method only takes 0.035 seconds. Update: Even another way to do it, which avoids the sort:

  [AI,AJ,AV] = find(A);                                                                                   
  A_i = sparse(AI,AJ,AV.^-1,size(A,1),size(A,2));                                                         
  [maxA_i,maxI_i] = max(A_i);                                                                             
  [minA,minI] = min(A);                                                                                   
  minA(minA==0) = inf;                                                                                    
  mA = [maxA_i.^-1;minA];                                                                                 
  [mA,J] = min(mA);                                                                                       
  mI = [maxI_i;minI];                                                                                     
  mI = mI(sub2ind(size(I),J,1:size(mI,2)));