Fastest way to drop multiple rows and columns from SparseArrays

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.

• 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. – Henrik Schumacher May 13 '18 at 2:08
• @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. – b3m2a1 May 13 '18 at 2:12
• 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). – Henrik Schumacher May 13 '18 at 2:19
• @HenrikSchumacher yeah using Part for both the rows and the columns simultaneously is actually quite fast. Like .01s to update a 14400x14400 matrix. – b3m2a1 May 13 '18 at 2:20

With[{toKeep = Complement[Range[Length[sparse]], toDrop]},