7.1 Compressed row storage
Sparse matrices are represented in Stan using compressed row storage (CSR). For example, the matrix \[ A = \begin{bmatrix} 19 & 27 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 52 \\ 81 & 0 & 95 & 33 \end{bmatrix} \] is translated into a vector of the non-zero real values, read by row from the matrix \(A\), \[ w(A) = \begin{bmatrix} 19 & 27 & 52 & 81 & 95 & 33 \end{bmatrix}^{\top} \! \! \! , \] an array of integer column indices for the values, \[ v(A) = \begin{bmatrix} 1 & 2 & 4 & 1 & 3 & 4 \end{bmatrix} \! , \] and an array of integer indices indicating where in \(w(A)\) a given row’s values start, \[ u(A) = \begin{bmatrix} 1 & 3 & 3 & 4 & 7 \end{bmatrix} \! , \] with a padded value at the end to guarantee that \[ u(A)[n+1] - u(A)[n] \] is the number of non-zero elements in row \(n\) of the matrix (here \(2\), \(0\), \(1\), and \(3\)). Note that because the second row has no non-zero elements both the second and third elements of \(u(A)\) correspond to the third element of \(w(A)\), which is \(52\). The values \((w(A), \, v(A), \, u(A))\) are sufficient to reconstruct \(A\).
The values are structured so that there is a real value and integer column index for each non-zero entry in the array, plus one integer for each row of the matrix, plus one for padding. There is also underlying storage for internal container pointers and sizes. The total memory usage is roughly \(12 K + M\) bytes plus a small constant overhead, which is often considerably fewer bytes than the \(M \times N\) required to store a dense matrix. Even more importantly, zero values do not introduce derivatives under multiplication or addition, so many storage and evaluation steps are saved when sparse matrices are multiplied.