# How to find k largest element and their position in a matrix?

I have a sparse matrix, and I am interested in find k largest elements and their positions in the matrix. I do it in the following manner:

matrix=SparseArray[Automatic, {4, 4}, 0, {
1, {{0, 2, 5, 8, 10}, {{2}, {3}, {1}, {3}, {4}, {1}, {2}, {4}, {2}, {
3}}}, {1.6608834828359216, 1.3176250784021715,
1.6608834828359216, 3.8979590937707167, 2.058499550409593,
1.3176250784021715, 3.8979590937707167, 1.0569052092863416,
2.058499550409593, 1.0569052092863416}}];
k = 2;
TakeLargest[Association@Most[ArrayRules[matrix]], k]


I look for a more efficient way to do it, any suggestion on how to speed up this calculation in huge matrices are welcome.

• @kglr I did not mean to diss you away. Your methods are still viable for dense matrices. – Henrik Schumacher Jul 15 '18 at 14:19
• @HenrikSchumacher, not to worry:) I deleted it because the question is explicitly about sparse arrays. – kglr Jul 15 '18 at 14:24

For sparse matrices, the key is to perform the search only on the list of nonzero values.

With[{idx = Ordering[matrix["NonzeroValues"], -k]},
matrix["NonzeroPositions"][[idx]],
matrix["NonzeroValues"][[idx]]
]
]


Beware that this completely neglects the zero valued entries.

# Remark

This will take postive effect only for really large and sparse matrices. For example, the following matrix would need 745 GB(!) of memory if it was stored (and sorted) as a dense array.

n = 100000;
m = 600000;
A = SparseArray[RandomInteger[{1, n}, {m, 2}] -> RandomReal[{0, 1}, m], {n, n}];
k = 100;


But still, finding the 100 largest nonzero elements needs about an 8th part of a second.

a = With[{idx = Ordering[A["NonzeroValues"], -k]},
A["NonzeroValues"][[idx]]]
]; // RepeatedTiming


0.124

# Edit

Incorporating Carl's and kglr's suggestion to use Nearest like in this post, we can get even faster:

a = With[{idx = Nearest[A["NonzeroValues"] -> Automatic, Max[A], k]},
A["NonzeroPositions"][[idx]],
A["NonzeroValues"][[idx]]
]
]; // RepeatedTiming // First


0.0051

Note that this returns the largest value first. Of course, we can Reverse the output of Nearest, if needed.

• Where are these properties documented as I don't see them in the SparseArray documentation. – Edmund Jul 15 '18 at 11:53
• @Edmund Sadly, they are documented nowhere. The more important are SE posts like this and this. I learnt these things solely from this site. What a shame! – Henrik Schumacher Jul 15 '18 at 12:46
• Ordering[matrix["NonzeroValues"], -k] with k greater than 1 will sort the data, and so it is quite slow. You could instead use Nearest[matrix["NonzeroValues"]->"Index", Max[data], k] as in my answer to (154944), which will be much faster when the nonzero length is large. – Carl Woll Jul 15 '18 at 12:53
• Carl, very good point! Wouldn't that suggest the reimplementation of the two-argument version of Ordering, at least for vectors? – Henrik Schumacher Jul 15 '18 at 13:06