16
$\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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Are the additions structure preserving? When you add a matrix with the same non-zero elements to a sparse matrix, a good implementation should be able to avoid costly operations. When it changes the sparsity structure, the addition can become quite expensive. On the other hand, adding two dense matrices that contain a lot of zeros is inefficient as well and rebuilding a new sparse matrix may be less expensive. $\endgroup$
    – allo
    Commented Jul 30, 2020 at 12:31

3 Answers 3

Reset to default
16
$\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.

Improve this answer
$\endgroup$
10
  • 1
    $\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
    Commented Sep 15, 2018 at 0:19
  • 4
    $\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
    Commented Sep 15, 2018 at 2:38
  • 5
    $\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
    Commented Sep 15, 2018 at 3:10
  • 7
    $\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
    Commented Sep 16, 2018 at 17:09
  • 2
    $\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
    Commented Sep 17, 2018 at 14:40
20
$\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.

Improve this answer
$\endgroup$
4
  • 1
    $\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$
    – josh_eime
    Commented Sep 15, 2018 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
    Commented Sep 15, 2018 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
    Commented Sep 15, 2018 at 16:48
  • 2
    $\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
    Commented Sep 16, 2018 at 1:44
7
$\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.

Improve this answer
$\endgroup$
2
  • 3
    $\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
    Commented Sep 17, 2018 at 13:02
  • 1
    $\begingroup$ Nice. That precisely the definition I tried to mimick, but I could not recall the source. $\endgroup$
    – Henrik Schumacher
    Commented Sep 17, 2018 at 13:43

Your Answer

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

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