Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
1  
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
up vote 12 down vote accepted

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]

sparse array screenshot

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.

share|improve this answer
    
Simple and fast! – becko Feb 23 at 16:24
3  
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
3  
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
2  
@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}]

enter image description here

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

share|improve this answer
    
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
2  
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 *)
share|improve this answer
1  
With the Table form dont'you extract only the first 9999 rows? – unlikely Feb 23 at 15:45
1  
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
1  
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}];

enter image description here

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

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

enter image description here

Hope this helps.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.