Java Reference
In-Depth Information
0
1
3
6
COLS
ROWS
0,0
0,1
0,6
0
10
23
19
0,3
1,1
1,3
1
45
5
93
0,4
4
40
7,1
7,3
7,6
7
32
7
12
Figure12.7
The orthogonal list sparse matrix representation.
the sparse matrix requires. The size of the sparse matrix depends on the number
of non-zero elements (we will refer to this value as NNZ), while the size of the
standard matrix representation does not vary. We need to know the (relative) sizes
of a pointer and a data value. For simplicity, our calculation will ignore the space
taken up by the row and column header (which is not much affected by the number
of elements in the sparse array).
As an example, assume that a data value, a row or column index, and a pointer
each require four bytes. An nm matrix requires 4nm bytes. The sparse matrix
requires 28 bytes per non-zero element (four pointers, two array indices, and one
data value). If we set X to be the percentage of non-zero elements, we can solve
for the value of X below which the sparse matrix representation is more space
efficient. Using the equation
28X = 4mn
and solving for X, we find that the sparse matrix using this implementation is more
space efficient when X < 1=7, that is, when less than about 14% of the elements
