2
$\begingroup$

Given $A\!\in\!\mathbb{Z}^{m\times n}$ stored as a=SparseArray[{...},{m,n}], how can I obtain the list of all indices $i\!\in\!\{1,\ldots,m\}$ for which the $i$-th row in $A$ is nonzero?

One option is DeleteDuplicates@Flatten@Transpose[a]["ColumnIndices"]. Is there a nicer way, or is this optimal?

$\endgroup$
2
$\begingroup$
Random`Private`PositionsOf[Unitize[Differences[a["RowPointers"]]], 1]

A timing example:

n = 100000;
m = 6000000;
a = AdjacencyMatrix@RandomGraph[{n, m}];
a[[RandomInteger[{1, n}, 1000], All]] = 0;

r = DeleteDuplicates@Flatten@Transpose[a]["ColumnIndices"]; // AbsoluteTiming // First
r1 = Random`Private`PositionsOf[Unitize[Differences[a["RowPointers"]]], 1]; // AbsoluteTiming // First
Sort[r] == r1

0.579587

0.002103

True

Edit

The undocumented function Random`Private`PositionsOf may be replaced by the following compiled function.

PositionsOfInteger = Compile[{{a, _Integer, 1}, {x, _Integer}},
   Block[{b, i = 0},
    b = Table[0, {Length[a]}];
    Do[If[Compile`GetElement[a, j] == x, b[[++i]] = j], {j, 1, 
      Length[a]}];
    If[i > 0, b[[1 ;; i]], Most[{0}]]
    ],
   CompilationTarget -> "C",
   RuntimeOptions -> "Speed"
   ];

Indeed, this turns out to be even a bit faster:

r2 = PositionsOfInteger[Unitize[Differences[a["RowPointers"]]], 1]; //
   AbsoluteTiming // First
r1 == r2

0.001647

True

$\endgroup$
  • $\begingroup$ What does "ColumnIndices" do? In this post, it says "gives the row pointers array from the compressed sparse row data", but I don't understand how it works. $\endgroup$ – Leon Jan 2 at 17:42
  • $\begingroup$ And what is this RandomPrivatePositionsOf? I can't find these commands in the documentation. $\endgroup$ – Leon Jan 2 at 18:03
  • $\begingroup$ In a nutshell, one has these relations (both expression evaluate to True): Flatten[a["ColumnIndices"]] == a["NonzeroPositions"][[All, 2]] and Prepend[Accumulate[Total[Unitize[a], {2}]], 0] == a["RowPointers"]. $\endgroup$ – Henrik Schumacher Jan 2 at 18:03
  • 1
    $\begingroup$ There is no documentation on Random`Private`PositionsOf; it is an undocumented funtion. Random`Private`PositionsOf[#, 0] & does essentially the same as Flatten[Position[#, 0]] & - but it is ten times faster. $\endgroup$ – Henrik Schumacher Jan 2 at 18:05
  • 1
    $\begingroup$ Well, everything in Mathematica has a nonvanishing risk to be invalidated by future versions. However, for symbols in the "System`" context, this risk is rather small. While there are several prominent examples of undocumented symbols that appear to have been ''stable'' for several major realeases, the risk of future changes of these symbols is certainly much higher. This is why I added a compiled function PositionsOfInteger as substitute for Random`Private`PositionsOf. $\endgroup$ – Henrik Schumacher Jan 27 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.