# Find minimum *non-zero* entry in sparse matrix

## Alec Jacobson

## April 04, 2012

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 `inf`

s 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 `inf`

s method takes **40.5 seconds**, first converting the matrix to full format then replacing with `inf`

s 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)));
```