8
$\begingroup$

What is the relation of memory usage of a SparseArray and the number of its occupied positions?

Let's say you build a $100000000 \times 10$ SparseArray and fill the two positions $(1,1)$ and $(100000000,10)$ with a value:

num = 999999;  
idSparse = SparseArray[{{1, 1} -> num, {100000000, 10} -> num}]  

There are two elements in the array.

Memory usage is:

ByteCount[idSparse]  
  400000968  

Disk usage is:

Export["idSparse.rsa", idSparse];  
FileByteCount["idSparse.rsa"]  
  380  
$\endgroup$

2 Answers 2

9
$\begingroup$

Looking at the InputForm or FullForm of the expression which, while not equivalent to the internal data format, shows something of the structure and what is stored:

SparseArray[{{1, 1} -> 999, {5, 100} -> 999}] // InputForm
SparseArray[Automatic, {5, 100}, 0, {1, {{0, 1, 1, 1, 1, 2}, {{1}, {100}}}, {999, 999}}]

versus:

SparseArray[{{1, 1} -> 999, {100, 5} -> 999}] // InputForm
SparseArray[Automatic, {100, 
  5}, 0, {1, {{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}, {{1}, {5}}}, {999, 999}}]

shows that some limited data is stored for every row in the array.

Therefore your expression will take up much less space if it is entered as:

num = 999999;
idSparse = SparseArray[{{1, 1} -> num, {10, 100000000} -> num}];
ByteCount[idSparse]

784

Of course your program will need to account for the changed orientation.

$\endgroup$
5
  • $\begingroup$ Good find, didn't know that. $\endgroup$ May 22, 2013 at 8:57
  • $\begingroup$ OK. . .Very good. . .We may add that in the first way we get large a RAM and a small file, the second way we get a smal RAM usage and a large file. $\endgroup$ May 23, 2013 at 15:12
  • $\begingroup$ @HpR that's good information, but not very convenient. I wonder if there is another sparse array file format that matches Mathematica's behavior. Using Transpose on the small-type SparseArray makes it large (as expected), so that is not a solution. $\endgroup$
    – Mr.Wizard
    May 23, 2013 at 16:26
  • 1
    $\begingroup$ N.B. peering through the internal form of SparseArray[] quickly reveals that the storage format is the so-called "row-major" or Yale format. $\endgroup$ Jul 27, 2016 at 16:52
  • $\begingroup$ @J.M. Thank you! $\endgroup$
    – Mr.Wizard
    Jul 27, 2016 at 16:57
1
$\begingroup$

As others have pointed out, a two-dimensional SparseArray is stored in the CSR format (CSR = Compressed Sparse Row(-major)). Let's suppose you store an $m \times n$ matrix with $k$ nonzero entries. The actual data stored is

  1. an $m+1$-vector of Integers, the so-called row pointers;
  2. a $k$-vector of Integer, the so-called column indices;
  3. a $k$-vector of the nonzero values; typically, the entries are Integers, Real, Complexs. But it can be what ever you want;
  4. a $2$-vector storing the dimensions as Integers.

Mathematica's Integers are 64 bit = 8 byte in size (unless they are too large for 64 bit; then some other representation is chosen). Machine-precision Reals are 64 bit = 8 byte, too.

So roughly, the actual size should be

size = 8 (m+1) + 8 k + 8 k + 8 2

or

size = 8 (Length[A["RowPointers"]] + Length[A["ColumnIndices"]] + Length[A["NonzeroValues"]] + Length[A["Dimensions"]])

When I compare that with ByteCount[A], then get fairly the same number. The actual size ByteCount[A] is a couple of hundred bytes greater because each of theconstituting arrays probably its own dimensions (which are redundant, but not a big issue). Moreover, probably some meta-information and flags (for example for remembering that a matrix is symmetric) are also stored in the data structure. Maybe some padding, too, for data alignment. Oh, and I forgot to count in one copy of the default element. ;)

As you can see, there is always an array of size $m+1$ stored no matter how few nonzero entries there are. That's why it might be a good idea to store tall and skinny matrices in transposed form. The catch is that multiplying a sparse matrix with a vector from the right is typically a bit less expensive than multiplying the vector from the left to the transposed matrix. This has to do with the asymmetry in the CSR format.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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