Sparse Matrices (2019)
matteding.github.io
Sparse Matrices (2019)
1–10 of 21 posts
Re: Sparse Matrices (2019)
#2Nice post!
For completeness: Apache Arrow is also adding sparse tensors in c++ [1] and wrapping them with python [2] (although the documentation for Python might be a bit lacking at the moment).
[1] https://arrow.apache.org/docs/cpp/api/tensor.html?highlight=...
[2] https://github.com/apache/arrow/blob/master/python/pyarrow/t...
Re: Sparse Matrices (2019)
#3Another useful representation for them is B+ tree https://en.wikipedia.org/wiki/B%2B_tree
Can be a single tree for the matrix where keys are tuples of two integers. Or one tree per row, where keys are single integers, column index.
Unlike CSR, inserting elements is Log(n). RAM overhead is larger than CSR but still reasonable, much smaller than hash maps or red-black trees would be. Similar to CSR, reading rows is mostly sequential RAM reads i.e. pretty fast.
Re: Sparse Matrices (2019)
#4I've gotten the question in ML eng interviews 3 times: implement sparse vector and the respective dot product op. I always go for the handy DOK method.
Re: Sparse Matrices (2019)
#5I've gotten the question in ML eng interviews 3 times: implement sparse vector and the respective dot product op. I always go for the handy DOK method.
how one could prepare for such interviews? i know google is the place to start, but if you could point some source would really appreciate it!
Re: Sparse Matrices (2019)
#6[deleted]
Re: Sparse Matrices (2019)
#7for a decent introduction to sparse matrix computations, see Tim Davis lectures
Re: Sparse Matrices (2019)
#8Another useful representation for them is B+ tree https://en.wikipedia.org/wiki/B%2B_tree Can be a single tree for the matrix where keys are tuples of two integers. Or one tree per row, where keys are single integers, column index. Unlike CSR, inserting elements is Log(n). RAM overhead is larger than CSR but still reasonable, much smaller than hash maps or red-black trees would be. Similar to CSR, reading rows is mos…
But how often you want to "insert" elements in a sparse matrix? It seems like a very strange thing to do, I cannot imagine a situation where I would need to do that (during the lifetime of a sparse matrix).
Re: Sparse Matrices (2019)
#9“If the ratio of Number of Non-Zero (NNZ) elements to the size is less than 0.5, the matrix is sparse. While this is the mathematical definition, I will be using the term sparse for matrices with only NNZ elements and dense for matrices with all elements.”
No, this is not the mathematical definition. An n-by-n matrix is usually considered sparse if the number of nonzero elements is O(n). Which means that the ratio of nonzero elements goes to zero as the matrix grows.
Re: Sparse Matrices (2019)
#10Not mentioned in the article, the ELL format is very efficient for banded matrices.