Compressed sparse storage

Compressed sparse storage keeps a sparse matrix as numerical nonzero values, their row or column indices, and pointers to the start of each compressed column or row. It avoids allocating all $N^2$ entries. A sparse direct solver must additionally allocate possible fill-in predicted by symbolic factorization, because elimination can create entries absent from the input.

Compressed sparse row format stores a sparse $m\times n$ matrix using arrays of nonzero values, their column indices, and an array of $m+1$ row offsets. For zero-based row $i$, its entries occupy positions from $\mathrm{rowptr}[i]$ through $\mathrm{rowptr}[i+1]-1$.

For $A=\left(\begin{array}{ccc}0& 5& 0\\ 2& 0& 7\end{array}\right)$, one representation is $\mathrm{values}=(5,2,7)$, $\mathrm{col}=(1,0,2)$, $\mathrm{rowptr}=(0,1,3)$. Equal adjacent offsets encode an empty row. This permits matrix-vector product in $O(m+\mathrm{nnz})$ time without storing zeros. Whether columns are sorted or duplicates are permitted is an implementation convention.