Compressed Sparse Row (CSR): How do you store empty rows?

Question

How do you represent empty rows in CSR?

Suppose we have the following matrices:

* MATRIX 1 *
a 0 0
0 b 0
0 0 c

val = [ a b c ]
col = [ 0 1 2 ]
row = [ 0 1 2 ] <- makes sense!

—————————————————————   

* MATRIX 2 *
a b c
0 0 0
0 0 0

val = [ a b c ]
col = [ 0 1 2 ]
row = [ 0 ] <— makes sense…? but how about…

—————————————————————

* MATRIX 3 *
0 0 0
a b c
0 0 0

val = [ a b c ]
col = [ 0 1 2 ]
row = [ 0 ] <— wait… how do we differentiate between MATRIX 2 and MATRIX 3?

MATRIX 1 is intuitive, but how do we represent the difference between MATRIX 2 and MATRIX 3? Do we use a negative integer for spacing?

Thanks

Answer 1

Take a look at The Wikipedia page. The IA vector (or as you call it "row"), is defined as:

The array IA is of length m + 1. It is defined by this recursive definition:

• IA[0] = 0
• IA[i] = IA[i − 1] + (number of nonzero elements on the (i − 1)-th row in the original matrix)
• Thus, the first m elements of IA store the index into A of the first nonzero element in each row of M, and the last element IA[m] stores NNZ, the number of elements in A, which can be also thought of as the index in A of first element of a phantom row just beyond the end of the matrix M. The values of the i-th row of the original matrix is read from the elements A[IA[i]] to A[IA[i + 1] − 1] (inclusive on both ends), i.e. from the start of one row to the last index just before the start of the next.

Thus, in Matrix 1:

row = [0 1 2 3]

in Matrix 2:

row = [0 3 3 3]

in Matrix 3

row = [0 0 3 3]