9
$\begingroup$

Suppose I know the expected sparsity of a matrix (i.e. the number of non-zeros / total possible number of non-zeros). Is there a rule of thumb (perhaps approximate) for deciding whether to use sparse matrix storage (specifically, compressed row storage) vs. storing it as a dense matrix?

  1. Speed is more important in my application than memory. But out of general curiosity, I'm interested in answers from both a speed and memory perspective.
  2. After generating the matrix, I only apply addition and multiplication operations on it.
  3. I have only been able to find qualitative answers, e.g. this question and this question but I'm looking for something like

...if the sparsity is more than approximately $x\%$, then use dense storage.

$\endgroup$
7
$\begingroup$

All matrix operations are memory bound (and not compute bound) on today's processors. So basically, you have to ask which format stores fewer bytes. This is easy to compute:

  • For a full matrix, you store 8 bytes (one double) per entry
  • For a sparse matrix, you store 12 bytes per entry (one double for the value, and one integer for the column index of the entry).

In other words, if your sparsity is below 67% -- i.e., for nearly any matrix any reasonable person would call sparse --, the sparse matrix format will not only yield better memory use but also better compute time.

$\endgroup$
  • $\begingroup$ I would like to hear why someone has downvotes this answer. It’s qualitative, quantitative, and gives a good rule of thumb. If I could upvote it twice, I would. $\endgroup$ – Charles Sep 15 '18 at 0:19
  • 3
    $\begingroup$ You’ll need slightly more storage than that- you need to keep track of the rows too. One bit per row is sufficient. $\endgroup$ – Brian Borchers Sep 15 '18 at 2:38
  • 3
    $\begingroup$ Matrix-matrix multiplication of dense matrices is one place where you get sufficient cache reuse that you can get very close to peak FLOPS. I agree that matrix vector multiplication will be memory bandwidth limited. $\endgroup$ – Brian Borchers Sep 15 '18 at 3:10
  • 1
    $\begingroup$ 67% is actually very far away from the point where computations would profit from sparsity. Dense matrix-vector multiplication can profit to a significantly greater extent from caching. (You need very irregular memory access for sparse matrix-vector multiplication.) If it is about solving linear systems with a direct solver, people sometimes say that a matrix is sparse if it has less than 0.1% of nonzero values. But in practice, the actual connectivity of the matrix entries is much more important than the number of nonzeros. $\endgroup$ – Henrik Schumacher Sep 16 '18 at 17:09
  • 1
    $\begingroup$ @WolfgangBangerth: Your definition of sparse ("Sparse" means that the number of nonzero entries per row is independent of the size for a set of matrices that grow larger and larger.), differs quite a bit from J.H. Wilkinson's (informal working) definition: "any matrix with enough zeros that it pays to take advantage of them", which is often cited in literature. I prefer Wilkinson's definition. $\endgroup$ – wim Sep 17 '18 at 14:40
11
$\begingroup$

For what it is worth, for random sparse matrices of size 10,000 by 10,000 vs. dense matrices of the same size, on my Xeon workstation using MATLAB and Intel MKL as the BLAS, the sparse matrix-vector multiply was faster for densities of 15% or less. At 67% (as proposed by another answer), the dense matrix-vector multiplication was about three time faster.

$\endgroup$
  • $\begingroup$ Interesting, thanks. Some of my matrices are up to 30-40% sparse (inconveniently right in between the 15% and 67% estimates), so I should probably conduct tests similar to yours (for the operations I'm interested in) to see if the memory advantages are worth the slow down. $\endgroup$ – EM_IE Sep 15 '18 at 3:17
  • 3
    $\begingroup$ A lot will depend on the hardware and software you’re using. My machine has quad channel memory so it has more memory bandwidth than a typical dual channel system. MKL is a very good BLAS and MATLAB’s sparse matrix data structures might not be perfectly optimized for this. $\endgroup$ – Brian Borchers Sep 15 '18 at 3:25
  • 1
    $\begingroup$ One problem with compressed row storage (or compressed column storage) is that the entries are usually stored in a different area in memory from the index information. This lack of locality can hurt performance. In comparison, in conventional dense matrix storage (by rows (C) or columns (Fortran)), you can load entries of the matrix consecutively from memory in a more efficient way. $\endgroup$ – Brian Borchers Sep 15 '18 at 16:48
  • 1
    $\begingroup$ In recent years there's been research on new storage formats for sparse matrices which enable enhanced performance for sparse matrix-vector multiplication on mutlcore processors, machines with SIMD instructions, and GPU's. See for example:pdfs.semanticscholar.org/041b/… $\endgroup$ – Brian Borchers Sep 16 '18 at 1:44
5
$\begingroup$

Even if a matrix is very sparse, its matrix product with itself can be dense. Take for example a diagonal matrix and fill its first row and column with nonzero entries; its product with itself will be completely dense. Such a matrix can arise, for examle, as graph Laplacian of a graph in which there is a vertex that is connected to all other vertices. In practice, it suffices if there are few vertices with pretty high connectivity to the rest of the network. For matrix-vector multiplication, this phenomenon is less relevant although it may lead to imbalances when trying to parallelize the matrix-vector multiplication.

What I want to highlight: It really depends on the sparsity pattern and on what you want to do with the matrix. So, the best definition of a sparse matrix that I can come up with (which is pretty useless at the same time) is as follows:

A matrix is sparse if it is advantageous to store only its nonzero values and their positions and to invest the additional overhead that is coming from managing the arising data structure.

The lesson to learn: It really depends on what you want to do with it, which algorithm you use, and (as others have already pointed out) which hard- and software you use whether a given matrix is sparse or not (read as: whether you should use a sparse or dense matrix data structure). There cannot be a purely percentage-based rule if it is not only about storing data or matrix-vector multiplication. The best way to find out if your matrices are sparse is just to try it and compare with dense matrix methods.

$\endgroup$
  • 1
    $\begingroup$ The famous J.H. Wilkinson defined a sparse matrix as: "any matrix with enough zeros that it pays to take advantage of them." Exactly this definition has been cited by others frequently. Nevertheless, your definition is also quite suitable. $\endgroup$ – wim Sep 17 '18 at 13:02
  • 1
    $\begingroup$ Nice. That precisely the definition I tried to mimick, but I could not recall the source. $\endgroup$ – Henrik Schumacher Sep 17 '18 at 13:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.