Compressed sparse row

Compressed sparse row (CSR) is a matrix storage format for sparse matrices that stores non-zero values in a single flat array and uses two auxiliary arrays to reconstruct the matrix structure. It is the dominant format for sparse linear algebra in scientific computing and graph analytics because it optimizes row-oriented operations — the most common access pattern in iterative solvers and matrix-vector multiplication.

The three arrays are: values (the non-zero entries in row-major order), column indices (the column of each entry), and row pointers (the index in the values array where each row begins). A row with no non-zero entries is represented by two identical row pointers, requiring no additional storage. This makes CSR a near-optimal compression: the storage cost is proportional to the number of non-zeros plus the number of rows, not the total matrix size.

The format is not without trade-offs. Column insertion is O(nnz) — potentially as expensive as rebuilding the matrix — because inserting a new non-zero shifts all subsequent entries. This is why CSR is used for static matrices and iterative algorithms that do not modify structure, while dynamic sparsity patterns use linked formats like LIL (list of lists) or coordinate format (COO) during construction, converting to CSR only after the matrix is finalized.

The CSR format is a systems-level reminder that representation determines performance. The same mathematical object — a sparse matrix — has dozens of storage formats, and the choice between them is not a detail but a design decision that can change asymptotic complexity by orders of magnitude.