6
$\begingroup$

When two SparseArrays are added together and new zero values are created, these new zero values are reported as "NonzeroValues". Example, produced with Mathematica version 10.2:

tst = SparseArray[{1, 0, 1, 0, 1}] - SparseArray[{1, 0, 1, 0, 1}];

tst["NonzeroValues"]
{0, 0, 0}

tst["NonzeroPositions"]
{{1}, {3}, {5}}

It appears that SparseArrays constructed in this way can become "polluted" with lots of false non-zeros. Is there a way to get Mathematica to quickly compact such a SparseArray and strip out the introduced zeros? In my application, I produce large sparse vectors through many such additions, and I need to quickly identify the positions of nonzero entries.

Edit: My application is similar to RowReduce. I have a large sparse matrix of mostly zeros and ones, and I am implementing pivoting, with selection rules based on the number of nonzero elements in the rows and columns. After a pivot, the number of nonzero elements will change for many of the rows of the matrix. My matrices have hundreds of rows and columns, with densities of around 1%.

$\endgroup$
10
$\begingroup$

Re-applying SparseArray[] to a matrix or vector generated in this way usually restores the sparsity.

p = SparseArray[{Band[{1, 1}] -> {1, 2, 4}, Band[{2, 1}] -> {5, -3}}, {3, 3}];
q = SparseArray[{{2, 2} -> -2, {3, 2} -> 3, {3, 1} -> -1}, {3, 3}];

r = p + q;
rs = SparseArray[r];

Complement[r["NonzeroPositions"], rs["NonzeroPositions"]]
   {{2, 2}, {3, 2}}
$\endgroup$
  • $\begingroup$ This solves the problem, but it requires recreation of the entire SparseArray. In my application, the number of nonzero elements is in the thousands or tens of thousands. Perhaps Mathematica's SparseArray implementation simply does not give a better way to do this. $\endgroup$ – dcutrell Oct 17 '15 at 2:49
  • $\begingroup$ I'm not aware of any tidier way, either. In this example, of course, I could have done r = SparseArray[p + q]; directly; I just wanted to demonstrate that the new zeroes do get recognized. $\endgroup$ – J. M. is away Oct 17 '15 at 2:52
  • 1
    $\begingroup$ @J.M. The only rationale that come to mind is performance of finding zero positions after every modification of SparseArray: it would be logical to determine such things only when it is necessary, not on every stage of computation with SparseArrays. That is the reason for my question: is it "by design" and the user have to apply SparseArray to the final result before using things like "NonzeroPositions" or is it a bug? Earlier I thought that "NonzeroPositions" aren't stored and calculated on the fly. $\endgroup$ – Alexey Popkov Oct 17 '15 at 8:22
  • 2
    $\begingroup$ @AlexeyPopkov I would like to remind that the whole "Nonzero*" are undocumented, thus should be immune from prosecution. :) $\endgroup$ – Silvia Oct 17 '15 at 13:23
  • 1
    $\begingroup$ @dcutrell That's really a theory, but you have not shown any evidence for it. If you really worry about it, then you can do this: write a LibraryLink function that uses Shared passing, to ensure no copy will be made, call MSparseArray_resetImplicitValues on it, the return. But once again: 1. What evidence do you have to show that this is not what happens when you do sa = SparseArray[sa]? 2. Are you sure that the recomputing can at all be done without a temporary internal copy? If yes, explain why. Based on my limited familiarity with the SparseArray internal structure, ... $\endgroup$ – Szabolcs Oct 18 '15 at 17:47

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.