Sparse Matrices (2019)

https://matteding.github.io/2019/04/25/sparse-matrices

by tremguy • 6 years ago

120 19 6 years ago

matteding.github.io

mihevc2• 6 years ago

Nice 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...

Const-me3• 6 years ago

Another 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.

enriquto2• 6 years ago

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).

Const-me3• 6 years ago

I’m not saying B+ tree is the best structure for them. Just another one to consider. Which one is the best depends on use case.

I used these trees in the code that builds large sparse matrices from something else. The domain was CAM/CAE, it was finite elements. As a nice side effect, with one tree per row I was able to parallelize the construction of that matrix, as different CPU cores can update different rows of the matrix in parallel.

amelius2• 6 years ago

How about the PageRank algorithm, where your crawler detects new links and you need to insert new weights into the matrix from which you then later compute page ranks?

tobmlt• 6 years ago

Finite element assembly is one I see daily. There are many times In computational mechanics and also mesh manipulation (graphics programming, shape design, etc) when inserting into a sparse matrix is useful.

eggie5• 6 years ago

I'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.

rmelhem2• 6 years ago

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!

im3w1l2• 6 years ago

I think you are missing one of the two pieces the question builds on: Linear Algebra (do you know how a dot product is defined?) or Datastructures including their complexity. You would prepare by reading up on whichever of these two you are missing.

If you know how it's supposed to work in theory but struggle to bang it out, you could do eg leetcode.

teacpde• 6 years ago

I got the same question in a non-ml interview (although the interviewer works on ml), DOK is the solution I naturally thought of. But that isn’t enough, the interviewer was looking for LIL for less overhead and type uniformity.

golovashkin• 6 years ago

for a decent introduction to sparse matrix computations, see Tim Davis lectures

https://www.youtube.com/watch?v=1dGRTOwBkQs

layoutIfNeeded• 6 years ago

“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.

mindv0rtex• 6 years ago

Not mentioned in the article, the ELL format is very efficient for banded matrices.

mihevc2• 6 years ago

Yet another format is CSF (Compressed Sparse Fiber): http://glaros.dtc.umn.edu/gkhome/node/1177

It's a generalized CSR/CSC (to ndim > 2) format that uses a tree data structure where each path from root to leaf encodes a nonzero element.

Sparse Matrices (2019)

Related Stories