How to convert a sparse matrix to a list of sparse arrays?

Question

I have a matrix stored as a SparseArray. How can I convert it to a List of its rows, where each row is stored as a SparseArray?

Note that the matrix is huge, so the conversion should use as little memory as possible (the lower bound being the memory of the final List object).

Answer 1

List @@ s will do the trick:

s = 1000000 // RandomInteger[{1, 1000000}, {#, 2}] -> RandomReal[1, #]& // SparseArray;

s // Head
(* SparseArray *)

s // Dimensions
(* {1000000, 1000000} *)

l = List @@ s;

l // Head
(* List *)

l // Dimensions
(* {1000000, 1000000} *)

l // First // Head
(* SparseArray *)

Take[l, 4]

Why Does This Work?

Commentators observe that replacing the head of the (apparent) FullForm of a SparseArray ought to produce a nonsensical result. Why, then, does this work?

Despite appearances, a SparseArray is an atom:

SparseArray[Range[10]] // AtomQ
(* True *)

The full-form is therefore synthetic. Any operations that operate upon the (notionally non-existent) subparts of these atoms are implemented as special definitions. The documentation strongly implies that a SparseArray is meant to act virtually interchangeably with a regular List.

The Details section gives explicit examples where the parts of a multidimensional sparse array themselves appear as sparse arrays to operations like Map, Part, Listable, etc. In light of this, it stands to reason that replacing the notional head of a multidimensional sparse array with List would result in a list of sparse arrays. It is likely that the implementation has explicit code to handle this case.

I cannot point to a definitive statement in the documentation that guarantees the behaviour of List @@ s. But I would argue that it is so strongly implied that it would be a regression if it were changed in some future release.

Answer 2

Easy to do with Map.

This generates a random sparse matrix(array):

{m, n} = {1000, 2000};
pairs = Flatten[
   Outer[List, RandomInteger[{1, m}, Floor[0.7 m]], 
    RandomInteger[{1, n}, Floor[0.7 n]]], 1];
smat = SparseArray[
  Thread[pairs -> RandomReal[{0, 1}, Length[pairs]]], {m, n}]

Get the rows:

vecs = Map[# &, smat];

Verify it is all sparse arrays:

Shallow[Head /@ vecs]

(* Out[170]//Shallow= {SparseArray, SparseArray, SparseArray, \
SparseArray, SparseArray, SparseArray, SparseArray, SparseArray, \
SparseArray, SparseArray, <<990>>} *)

Here is some profiling code:

Profiling code:

memOld = MemoryInUse[];
timeOld = Date[];
vecs = Map[# &, smat];
memNew = MemoryInUse[];
timeNew = Date[];

(memNew - memOld)
(memNew - memOld)/memOld // N
timeNew - timeOld  

(* 12172576

   0.170369

  {0, 0, 0, 0, 0, 0.021384} *)

(I got the output on a 2.3 GHz Intel Core i7 MacBook Pro laptop with Mathematica 10.3.2.)

Answer 3

@WReach has provided the ultimate answer. Consider this an extended comment about the performance of ArrayRules

---

A large SparseArray

sa = SparseArray[
   Table[
    RandomInteger[{1, 99999}, 2] -> RandomReal[1]
    , 9999]
   ];

An example with Table that takes some time even for a subset of the rows (some list will be empty).

First@AbsoluteTiming[Table[sa[[k]], {k, 9999}]]
(* 2.68629 *)

But if you can get away with ArrayRules instead of SparseArray

First@AbsoluteTiming[GatherBy[Most@ArrayRules[sa], First@*First]]
(* 0.0172612 *)

Answer 4

If m contains your SparseArray

m = SparseArray[{{1, 2} -> a, {3, 2} -> b, {3, 3} -> c}];

then the following will return its list of sparse array rows.

m[[#]] & /@ Range[First@Dimensions@m]

Hope this helps.