# What is the conventional approach for sparse matrix multiplication?

When you're multiplying sparse matrices against other sparse matrices or dense matrices, what is the conventional approach for each? How are the sparse matrices stored? What does matrix multiplication work?

My understanding is there are several ways it can be stored:

(1) Store the non-zero elements in a hash table where the key is the 2D indices (mapped to 1D usually) and the value is the value of the non-zero element at that index.

(2) Store the non-zero elements in a $$k$$ sized array where $$k$$ is the number of non-zero elements. Each element stores the indices and the value at that index.

(3) Similar to (2), but you have a $$n$$ sized array where $$n$$ is the size of the original matrix. For each element of the array you store a list of non-zero elements.

I'm not sure which of these or some other formulation is used in practice and under what circumstances.

An additional question I have is do we know how this is done in linear algebra packages like BLAS and LAPACK?

• BLAS and LAPACK don't support sparse matrix operations. It is difficult to get good performance in sparse matrix-matrix multiplication (SPMM)- you can find many papers on the topic. Aug 23, 2021 at 2:25
• @BrianBorchers I'll do some literature review on this. Is there a quick 1-3 sentence summary you could give on why good performance is difficult with SPMM? Does BLAS and LAPACK just default to everything as if it were a dense matrix operation Aug 23, 2021 at 2:42
• @anonuser01, there is no interface to input a sparse matrix into BLAS/LAPACK. Sparse matrix operations are simply not implemented in those. Aug 23, 2021 at 2:49
• BLAS and LAPACK only perform dense matrix operations. Aug 23, 2021 at 4:18
• The conventional approach for sparse matrix-matrix multiplication is: don't do it. :p Reframe all your operations as matrix-vector multiplications using associativity, or Schur complements of larger matrices. Aug 23, 2021 at 7:38

• There are many technical details, like hundreds -if not thousands- of papers full of issues related to SpM-SpM. But the simplest one is related to how sparse matrices are stored. You just store the nonzeros, so when you try, say, $C_{ik} = \sum_j A_{ij}B_{jk}$ you have to go and "search" for the entries $A_{ij}$ and $B_{jk}$. That is the first issue, say you solved it. Now you have a new problem, allocate new memory to store each nonzero $C_{ik}$. Because ideally, you want to store $C$ as a sparse matrix too. But you don't know which entries are nonzero before you do the multiplication. Aug 23, 2021 at 2:57