4 ms·

To get the best performance you typically want to know something about the sparsity structure of your problem. Do most nonzeros fall near the diagonal? Or do th

by perimo 8y ago

To get the best performance you typically want to know something about the sparsity structure of your problem. Do most nonzeros fall near the diagonal? Or do they clump into dense submatrices? If you don't have that information, you can look at how your matrix will be accessed. Do you need fast access to random rows, or columns? Do you need to write new values? Are those values already in the sparsity structure? All of these questions can lead you to choosing the right sparse format, but it does take some experience to know where to look.

timr 8y ago
That's true, but mostly you just want to be able to store massive sparse matrices without filling your RAM with zeros (or spending tons of time reading/writing zeros from disk). Any implementation will do, as long as it works.
- srean 8y ago
  Storage is a minor worry. The main thing is whether the storage makes the frequent operations efficient. The tuple (index_position, value) is reasonably storage efficient but abysmal for linear algebraic operations. So one cannot decouple storage efficiency concerns from compute concerns too much. I think this is one of those shibboleths that separate folks who are experts in ML/data-science at scale vs those who are coming more from a enterprise/DBA background. I often have to convince folks why its not a great idea to write sparse matrix multiplication in SQL.
  - timr 8y ago
    "Storage is a minor worry." For many domains, it's a big worry. I routinely encounter large, sparse datasets where I/O and storage dominate other concerns. Big sparse tensors are worse than the "slowness" associated with a suboptimal sparse vector math implementation. "I think this is one of those shibboleths that separate folks who are experts in ML/data-science at scale vs those who are coming more from a enterprise/DBA background." I've been doing ML work for a long time. This is actually a shibboleth that separates folks who mostly do image classification from other kinds of ML people.
    - srean 8y ago
      "Minor" in the sense relatively easy to solve if not constrained by the compute needs. Interesting comment regarding image classification. I would have assumed they are the ones who don't have to worry about sparsity much. Physics, and image and video are some of the places you encounter large and dense matrices. Lapack's wet dream :)

by perimo 8y ago

timr 8y ago

That's true, but mostly you just want to be able to store massive sparse matrices without filling your RAM with zeros (or spending tons of time reading/writing zeros from disk). Any implementation will do, as long as it works.

srean 8y ago
Storage is a minor worry. The main thing is whether the storage makes the frequent operations efficient. The tuple (index_position, value) is reasonably storage efficient but abysmal for linear algebraic operations. So one cannot decouple storage efficiency concerns from compute concerns too much. I think this is one of those shibboleths that separate folks who are experts in ML/data-science at scale vs those who are coming more from a enterprise/DBA background. I often have to convince folks why its not a great idea to write sparse matrix multiplication in SQL.
- timr 8y ago
  "Storage is a minor worry." For many domains, it's a big worry. I routinely encounter large, sparse datasets where I/O and storage dominate other concerns. Big sparse tensors are worse than the "slowness" associated with a suboptimal sparse vector math implementation. "I think this is one of those shibboleths that separate folks who are experts in ML/data-science at scale vs those who are coming more from a enterprise/DBA background." I've been doing ML work for a long time. This is actually a shibboleth that separates folks who mostly do image classification from other kinds of ML people.
  - srean 8y ago
    "Minor" in the sense relatively easy to solve if not constrained by the compute needs. Interesting comment regarding image classification. I would have assumed they are the ones who don't have to worry about sparsity much. Physics, and image and video are some of the places you encounter large and dense matrices. Lapack's wet dream :)