6
$\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?

Improve this question
$\endgroup$
5
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 14:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.