5
$\begingroup$

I would like to prune some unimportant rows and columns from a SparseArray to accelerate solving some eigenvalue problems.

Given

sparse =
 KroneckerProduct[RandomReal[{-10, 10}, {30, 30}], 
   IdentityMatrix[30, SparseArray]] + 
  KroneckerProduct[IdentityMatrix[30, SparseArray], 
   RandomReal[{-10, 10}, {30, 30}]]

I would like to drop a selection of rows and the paired up columns, say 600 of the 900:

toDrop = RandomSample[Range@900, 600];

Currently I'm using Drop as suggested in the documentation. Unfortunately this will only drop a span of rows and columns at once, so first I have to build an accumulated set of spans, which I've been doing like:

dropSpans =
  FoldList[
    {#[[1]] + #2[[2]] - #2[[1]] + 1, #2 - #[[1]]} &,
    {0, None},
    MinMax /@ Split[Sort@toDrop, (#2 - #) == 1 &]
    ][[2 ;;, 2]];

Then I have to Fold the Drop like:

Fold[Drop[#, #2, #2] &, sparse, dropSpans];

Now this is fine for the 30x30 case:

Fold[Drop[#, #2, #2] &, sparse, dropSpans]; // RepeatedTiming // First

0.090

But the since matrix size increases as $N^4$ for me here even by the time I'm feed in 120x120 base matrices it takes a full 120 seconds as I'm building a new SparseArray object for every step in Fold--and the number of steps also increases as $N^2$. If I could just drop all of the parts at once I assume this would be quite fast. I'm also hoping not to have to work with the internal SparseArray structure but that's fine if there's no other way.

$\endgroup$
  • 1
    $\begingroup$ I would use Part to extract the nondropped rows with the Complement of dropped indices as second argument. Delete might also work (with the full index set expanded; not with Spans). Quite likely, the first is what the latter does internally. So better try both. $\endgroup$ – Henrik Schumacher May 13 '18 at 2:08
  • $\begingroup$ @HenrikSchumacher unfortunately Delete appears to convert the array to dense array. I had assumed Part would be less efficient since in some sense there is more work being done with that, but I suppose the construction overhead of this method will overwhelm that. $\endgroup$ – b3m2a1 May 13 '18 at 2:12
  • $\begingroup$ Hm. I cannot confirm that, but anyways, A[[Complement[Range[Length[A]], idx]]] seems to be faster (A ist the matrix, idx the index set of vertices to delete). $\endgroup$ – Henrik Schumacher May 13 '18 at 2:19
  • $\begingroup$ @HenrikSchumacher yeah using Part for both the rows and the columns simultaneously is actually quite fast. Like .01s to update a 14400x14400 matrix. $\endgroup$ – b3m2a1 May 13 '18 at 2:20
3
$\begingroup$

My suggestion is

With[{toKeep = Complement[Range[Length[sparse]], toDrop]},
  sparse[[toKeep, toKeep]]
  ];
$\endgroup$
  • $\begingroup$ Works wonderfully. $\endgroup$ – b3m2a1 May 13 '18 at 20:51

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.