Sparse Matrix Operations
For sparse matrices, for which many elements are zero, it is more efficient to use specialized representations to save memory and speed up matrix arithmetic (including derivative calculations). Given Stan’s implementation, there is substantial space (memory) savings by using sparse matrices. Because of the ease of optimizing dense matrix operations, speed improvements only arise at 90% or even greater sparsity; below that level, dense matrices are faster but use more memory.
Because of this speedup and space savings, it may even be useful to read in a dense matrix and convert it to a sparse matrix before multiplying it by a vector. This chapter covers a very specific form of sparsity consisting of a sparse matrix multiplied by a dense vector.
Compressed row storage
Sparse matrices are represented in Stan using compressed row storage (CSR). For example, the matrix
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
Conversion functions
Conversion functions between dense and sparse matrices are provided.
Dense to sparse conversion
Converting a dense matrix
vector
csr_extract_w
(matrix a)
Return non-zero values in matrix a; see section compressed row storage.
array[] int
csr_extract_v
(matrix a)
Return column indices for values in csr_extract_w(a)
; see compressed row storage.
array[] int
csr_extract_u
(matrix a)
Return array of row starting indices for entries in csr_extract_w(a)
followed by the size of csr_extract_w(a)
plus one; see section compressed row storage.
tuple(vector, array[] int, array[] int)
csr_extract
(matrix a)
Return all three components of the CSR representation of the matrix a
; see section compressed row storage. This function is equivalent to (csr_extract_w(a), csr_extract_v(a), csr_extract_u(a))
.
Sparse to dense conversion
To convert a sparse matrix representation to a dense matrix, there is a single function.
matrix
csr_to_dense_matrix
(int m, int n, vector w, array[] int v, array[] int u)
Return dense
Sparse matrix arithmetic
Sparse matrix multiplication
The only supported operation is the multiplication of a sparse matrix
vector
csr_matrix_times_vector
(int m, int n, vector w, array[] int v, array[] int u, vector b)
Multiply the