Compressed sparse row

Construction

This note is under construction.

Link

This note lacks links.

Citation

This note lacks citations.

Tag

This note lacks tags.

Storage

This note is not stored correctly.

In {{field}}, the compressed sparse row (CSR) ^[1] format is a sparse matrix format and one of the most commonly used.

• Three vectors are required for storing the matrix in a compressed manner. One holds the column indices and the other one is used to store the non-zero values itself. The elements are stored using row-major order. The $n$-th element of the vector points to the first element of the $n$-th row. This allows a very fast access to all elements of a given row. Additionally the vector can be used to calculate the number of non-zero elements per row. This can be done by subtracting the offset of the row from the offset of the next row. The vector contains one additional element at the end, which points directly behind the last element of the last row. Because of this, the number of elements in the last row can also be calculated.

• The CSR format can be traversed by rows, which allows the efficient parallelization of the sparse matrix-vector multiplication (SpMV) operation.
• The compressed sparse column (CSC) format is a similar storage-scheme as CSR. The elements are stored using column-major order instead of row-major order. Instead of the column indexes, the row indexes are stored. This allows the CSC format to be traversed by its columns.

Memory demand

---

Different data types can be used for storing the index data and the non-zero entries itself. In the memory demand $m_{CSR}$ these sizes are denoted as $S_{int}$ and $S_{float}$ and $N_{rows}$ describes the number of rows of the stored matrix:

$$m_{CSR}=nnz\cdot (S_{int}+S_{float})+(N_{rows}+1)\cdot S_{int}$$

The CSR format is more efficient compared to the COO format for most matrices, as it can be assumed, that there are much more non-zero elements compared to the number of rows.

References

1. [1]

   “Compressed sparse row”, Wikipedia, Available: https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format), Accessed: 2026-07-31 ↩