How to relate memory usage with occupied positions of SparseArrays?

Question

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  

Answer 1

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.

Answer 2

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.