# Sparse matrix format and sparse-matrix sparse-matrix multiplication

I'm having some performance problems with my code dealing with the multiplication of big sparse matrices (stiffness and aerodynamic influence coefficient matrices). Mainly I have to multiply such matrices frequently in my code with each other. Basically, one should of course not multiply sparse matrices but rather use matrix-vector multiplications. However, in my case, I can hardly prevent matrix-matrix multiplications.

Now... I get sparse matrices in CSC, CSR and COO formats as an input. (Not sensible as well, but I cannot influence this interface -.-). Are there rules of the thumb that help me decide which format the matrices in my multiplication should best have to end up with a high(er) performance code?

I know Intel's mkl_dcsrcsc (multiplies CSR-matrix with CSC-matrix) for example, cannot find a mkl_dcsccsr (multiplies CSC-matrix with CSR-matrix) on the other hand. Is it, therefore, sensible for $$A \cdot B$$ to convert $$A_\text{CSC}$$ from CSC-format into CSR-format $$A_\text{CSR}$$ and $$B_\text{CSR}$$ into $$B_\text{CSC}$$? Might it even be sensible to take a long way and convert $$A_\text{CSC}$$ to $$A_\text{CSR}$$ and $$B_\text{CSR}$$ to $$B_\text{COO}$$ (in order to enable mkl_dcsrcoo)?

How can I find out which format I should best use for my matrices and which functions/routines I should best use for my matrix-matrix multiplications?

• Why exactly do you need to multiply the matrices together? Are you then using the result to multiply against vectors? If so, I'd recommend using the property that $(AB)v = A(Bv)$. – Tyler Olsen Jun 23 '16 at 19:10
• As an additional note, the likely reason that MKL has the csr*csc multiplication built in is because it can be done reasonably efficiently. The rows of the csr and the columns of the csc are contiguous in memory, so it is a simple matter of matching up elements in these sparse arrays to produce an element of the resulting matrix. – Tyler Olsen Jun 23 '16 at 19:14
• After various multiplications I'll have to use it as the system matrix AB to solve a linear equation system $(AB)v = y$. Following your idea: $(AB)v = A(Bv) = y$ – murph_sof Jun 24 '16 at 14:36
• I'd need to solve 2 equation systems instead of multiplying matrices. However, I'll not save anything by this, right? (My system matrices differ in the two LES) – murph_sof Jun 24 '16 at 14:39
• It's hard to say anything concrete without seeing your system, but it may be that sequentially solving the system is faster than doing the multiplication, incurring potentially large fill-in, and factorizing the result. If you're using an iterative solver, spoof the matrix multiplication by using a "LinearOperator" type (of which [Sparse]Matrix is a sub-type), that supports the $(AB)v$ operation (implemented by doing $A(Bv)$). As always, the best course of action is to try both on a smaller problem and see which will generalize to large problems better. – Tyler Olsen Jun 24 '16 at 14:51