Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sparse Matrices (2019)

matteding.github.io

Post reply on HN
Print view View original

11–20 of 21 posts

Re: Sparse Matrices (2019)

#11

Post by Const-me »

enriquto wrote: post #8
Const-me wrote: post #3

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

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.

Re: Sparse Matrices (2019)

#12

Post by enriquto »

Const-me wrote: post #11
enriquto wrote: post #8

Earlier quoted context omitted.

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

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 th…

Sure, B+ trees are cool. I was just wondering about the use case for element insertion (except maybe for the construction of the matrix). Most of my time is spent in algebraic operations with immutable matrices.

Regarding the construction of the matrix, instead of insertions very often you can do it with tricks using kronecker products and the like.

Re: Sparse Matrices (2019)

#13

Post by Const-me »

enriquto wrote: post #12
Const-me wrote: post #11

Earlier quoted context omitted.

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 th…

Sure, B+ trees are cool. I was just wondering about the use case for element insertion (except maybe for the construction of the matrix). Most of my time is spent in algebraic operations with immutable matrices. Regarding the construction of the matrix, instead of insertions very often you can do it with tricks using kronecker products and the like.

> except maybe for the construction of the matrix

Yep, that’s precisely why I used that thing.

> Most of my time is spent in algebraic operations with immutable matrices.

CSR is probably the way to go then.

Also, if you do that math on CPU and your matrix is not randomly sparse but made of small dense areas of non-zeroes, consider less compressed SIMD-friendly variant of CSR, where instead of individual elements you keep dense SIMD vectors.

For example, if you have AVX and need fp64 precision, keep 4 elements long slices of rows there. This way you can use 256-bit loads and FMA instructions to do that math.

Or if you spending most of time multiplying matrices as opposed to matrix*vector, might be reasonable to keep 2x2 dense blocks as opposed to 4x1.

Re: Sparse Matrices (2019)

#14

Post by amelius »

enriquto wrote: post #8
Const-me wrote: post #3

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

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?

Re: Sparse Matrices (2019)

#15

Post by tobmlt »

enriquto wrote: post #8
Const-me wrote: post #3

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

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.

Re: Sparse Matrices (2019)

#16

Post by teacpde »

eggie5 wrote: post #4

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.

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.

Re: Sparse Matrices (2019)

#17

Post by im3w1l »

amelius wrote: post #14
enriquto wrote: post #8

Earlier quoted context omitted.

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

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?

Wouldn't it be easier to first do your crawling and then construct the matrix in one go? But graphs more broadly sounds like an area where you might want to update the matrix yeah.

Re: Sparse Matrices (2019)

#18

Post by im3w1l »

rmelhem wrote: post #5
eggie5 wrote: post #4

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.

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!

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.

Re: Sparse Matrices (2019)

#19

Post by amelius »

im3w1l wrote: post #17
amelius wrote: post #14

Earlier quoted context omitted.

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?

Wouldn't it be easier to first do your crawling and then construct the matrix in one go? But graphs more broadly sounds like an area where you might want to update the matrix yeah.

Well, one exception could be that some parts of the web need to be crawled more often than others.

But tbh, I think incremental updating of a matrix only makes sense if the other parts of your pipeline are also incrementalized.

Post reply on HN