1

Are there any algorithms that multiply dense and sparse matrices?

I've currently got 2 large matrices currently stored as dense matrices, one of the two is actually quite sparse (2/3rds 0's, and potentially even more sparse). The other is fully populated (e.g. dense).

Are there any speed efficiencies that can be gained by by doing dense x sparse multiplication (I'm unconcerned with space)? Are there any algorithms that handle it?

David Parks
  • 445
  • Let $D$ be the dense matrix and $S$ be the sparse matrix. Let $A=DS$. By definition, $a_{ij}=\sum_{k}d_{ik}s_{kj}$. The naive approach to compute $a_{ij}$ is thus to loop over the nonzeros $s_{*j}$. Should we assume you are looking for something non-naive? – parsiad Jun 08 '16 at 21:19
  • I mean to ask what has been built that's computationally efficient. Is it even possible to improve efficiency by exploiting the fact that one matrix is sparse and the other is not? If you have 2 sparse matrices the algorithm to multiply them is more expensive on a per-unit basis than the dense algorithm, but you do so many fewer steps so you end up with a savings. I don't know what computational efficiency would be from a sparse-dense matrix multiplication algorithm, if one even exists. I mean to explore the possibilities here. – David Parks Jun 08 '16 at 23:33
  • 1
    If both matrices are $n\times n$ and there are a constant number of nonzero entries per row $S$, the naive procedure I suggested in my comment takes constant time to compute each element $a_{ij}$ and hence takes quadratic time to compute $A$. (so yes, this is better than dense-dense multiplication) – parsiad Jun 09 '16 at 01:54

1 Answers1

1

Here is a distributed algorithm, but it works on a single processor machine as well: http://ieeexplore.ieee.org/document/7516081/

Code: http://people.eecs.berkeley.edu/~penpornk/spdm3/index.html

What is your application? I have been curious of other applications where this sparse x dense matrix multiplication algorithm would be useful

Sang
  • 111