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

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).

-
Like Table[SparseArray[Band[{1, 1}] -> 1, {4, 4}][[k]], {k, 4}]? – J. M. Feb 23 at 13:13
@J.M. Yes, that is the final representation I want. How do I convert an input sparse matrix to this form? – becko Feb 23 at 13:14
Well, you could replace the SparseArray[] in my snippet with yours, for example. – J. M. Feb 23 at 13:16
@J.M. This works and gives the result that I want. However, for some reason it is very slow for me. Maybe there is a faster way? – becko Feb 23 at 13:43
Can you give a (minimal?) example of a sparse matrix where this goes slow? – J. M. Feb 23 at 13:48

List @@ s will do the trick:

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

(* SparseArray *)

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

l = List @@ s;

(* List *)

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

(* 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.

-
Simple and fast! – becko Feb 23 at 16:24
Brilliant, but I don't understand why doest it work considering what is the FullForm of a SparseArray. Can you comment on the rationale behind? – rhermans Feb 23 at 16:33
Actually I didn't understand either, I was just happy it worked. I second @rhermans request for further explanation. – becko Feb 23 at 16:55
@rhermans I added the section Why Does This Work? – WReach Feb 23 at 18:33

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.)

-
Hah, I'd done it as Identity /@ smat myself, but I wasn't sure if it was faster or slower than Table[]. – J. M. Feb 23 at 14:19
I did some profiling: Identity /@ smat does not seem faster than #& /@ smat and it seems to be 10-20% less memory consuming. Of course the comparison should be done on a collection of sparse matrices with different sizes and densities. – Anton Antonov Feb 23 at 14:32

@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 *)

-
With the Table form dont'you extract only the first 9999 rows? – unlikely Feb 23 at 15:45
Yes, in the Table form you are missing most rows, that's why the timing is so small I think. – becko Feb 23 at 15:47
not a fair timing comparison unless you add the code to reconstruct the individual sparse arrays. – george2079 Feb 23 at 16:21
Yes, this of not for benchmark, times here are only to show that what is almost impossibly slow even for a subsection of a SparseArray becomes trivial with ArrayRules for the whole set. This may or may not be of use to the OP. – rhermans Feb 23 at 16:25

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.

-