5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Tyler Olsen Jun 23 '16 at 19:10
  • $\begingroup$ 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. $\endgroup$ – Tyler Olsen Jun 23 '16 at 19:14
  • $\begingroup$ 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$ $\endgroup$ – murph_sof Jun 24 '16 at 14:36
  • $\begingroup$ 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) $\endgroup$ – murph_sof Jun 24 '16 at 14:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Tyler Olsen Jun 24 '16 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.