I'm trying to figure out what the use cases are for sparse
matrices (not ragged data structures, not structured matrices
like triangular or tri-diagonal or anything else) before trying
to implement them.
So far, the only use case I can think of is to have a sparse
data matrix X, a dense parameter matrix beta, and compute
X * beta. That's what we already have hacked in with CSR.
What else are sparse matrices good for?
The problem I'm running into is that for parameters, transformed
parameters, and generated quantities, we need to fix the sparsity
pattern once and for all because Stan requires a fixed set of
parameters for I/O. Are there cases where local variables
or transformed data have varying sparsity over their scope?
Function arguments should be no problem, because those don't take sizes.
I'm imagining by analogy to matrices, e.g.,
matrix[4, 3] x;
I'd implement a sparse matrix the same way:
sparse_matrix[4, 3] x;
But that won't work for parameters because it doesn't fix the
sparsity pattern. Instead, I could take an array of non-zero
int nz[J, 2];
that indicates J non-zero positions, then declare a sparse
sparse_matrix[M, N, nz];
to say that it's M x N and the non-zero entries are as given in nz.
Then we'd throw exceptions if anything is assigned to the
zero positions or if any of the nz[j] are outside M x N.
But that'd prohibit doing things like adding or multiplying sparse
matrices unless we could compute the sparsity pattern ahead of time
for the declaration.