# Understanding the CRS Matrix format

The compressed row storage (CRS) format is a matrix storage format for sparse matrices, which is most useful for matrices which have a linear number of non-zero elements (compared to dense matrices having a quadratic number of non-zero elements).

### Storage

The format takes a $n \times m$ matrix $A$ and turns it into the following arrays:

- The
`val`

array stores all the values of the non-zero elements of the matrix, therefore it has length $\textrm{nnz}(A)$ (the number of non-zero elements in $A$) - The
`col_ind`

array stores for each non-zero element of the matrix the column index it is in, therefore it has length $\textrm{nnz}(A)$ - The
`row_ptr`

array stores for each*row*when that row starts in the other two arrays, plus it always ends with the sentinel value, therefore it has length of $\textrm{rows}(A) + 1 = n + 1$

Therefore, the number of values we need to store a $n \times m$ matrix is $$2 \cdot \textrm{nnz}(A) + n + 1$$

### Examples

$$ \begin{pmatrix} 1 & 0 & 2 \\ 3 & 4 & 5 \\ 0 & 0 & 0 \\ 0 & 0 & 6 \end{pmatrix} $$ We start with

`val = []`

`col = []`

`row_ptr = [1]`

The $1$ in the`row_ptr`

array indicates that we are starting the first row with the first element in`val`

(which has yet to be added). Also notice that we are doing $1$-indexing here.

Now go through the first row, the $1$ is in the first column, so we get

`val = [1]`

`col = [1]`

`row_ptr = [1]`

The $2$ is in the third column, so we get

`val = [1, 2]`

`col = [1, 3]`

`row_ptr = [1]`

Now we reach the end of the row, which means the next row will start with the *third* elements in `val`

and `col`

(because the first two elements belong to the first row).

`val = [1, 2]`

`col = [1, 3]`

`row_ptr = [1, 3]`

After the next row:

`val = [1, 2, 3, 4, 5]`

`col = [1, 3, 1, 2, 3]`

`row_ptr = [1, 3, 6]`

The next row is all zeroes, so all we will be adding is another $6$ to `row_ptr`

:

`val = [1, 2, 3, 4, 5]`

`col = [1, 3, 1, 2, 3]`

`row_ptr = [1, 3, 6, 6]`

And finally, after the last row:

`val = [1, 2, 3, 4, 5, 6]`

`col = [1, 3, 1, 2, 3, 3]`

`row_ptr = [1, 3, 6, 6, 7]`

Here is another example: $$ \begin{pmatrix} 1 & 0 & 4 \\ 2 & 0 & 5 \\ 3 & 0 & 6 \end{pmatrix} $$

`val = [1, 4, 2, 5, 3, 6]`

`col = [1, 3, 1, 3, 1, 3]`

`row_ptr = [1, 3, 5, 7]`

### Interesting specifics

- Adding an empty row to a matrix, means adding an element to
`row_ptr`

, adding an empty column, uses no additional storage - The first element of
`row_ptr`

is always $1$, the last element (the sentinel value) is always $\textrm{nnz}(A)+1$ - The sentinel value could be inferred by other things (e.g., length of
`row_ptr`

) but we store it because it simplifies the specification of the format and the implementation of operations within it

### Compressed Column Storage

The sister format of compressed row storage is compressed column storage. The format is almost self-explanatory. Instead of going row-wise through the matrix and storing `col`

and `row_ptr`

we store `row`

and `col_ptr`

.

$$ \begin{pmatrix} 1 & 0 & 4 \\ 2 & 0 & 5 \\ 3 & 0 & 6 \end{pmatrix} $$ Becomes:

`val = [1, 2, 3, 4, 5, 6]`

`row = [1, 2, 3, 1, 2, 3]`

`col_ptr = [1, 4, 4, 7]`