3 ms·
> Raising graph analysis to the level of linear algebra is brilliant. Adjacency matrices is how graph problems were handled by APL programmers in the 1980s, mo
by sedachv 8y ago
> Raising graph analysis to the level of linear algebra is brilliant.
Adjacency matrices is how graph problems were handled by APL programmers in the 1980s, mostly because there was no alternative before nested arrays. At the time, there was not a lot of vectorized hardware, and main memory sizes were too small for many problems, so the adjacency matrix representation was more of a problem than a good solution. It's really the advances in vectorized hardware and main memory sizes that have made this technique practical for large graphs.
- espeed 8y agoYes, a lot of innovation had to occur to make the GraphBLAS linear algebra model practical, which has been in the works for more than 10 years. It began with Jeremy Kepner and John Gilbert's work formalizing the linear algebra model over semi-rings [1]. And then working with Intel, IBM, Nvidia and the other hardware vendors to define and implement a standard set of hardware primitives. But you could really see the stars align a few years ago then when the deep-learning ML wave hit because it paved the way with a surge in demand for GPU/TPU accelerators in the data center. A lot of things had to happen in to make this all come together. It's been an industry-wide effort. [1] Graph Algorithms in the Language of Linear Algebra, by Jeremy Kepner and John Gilbert https://epubs.siam.org/doi/book/10.1137/1.9780898719918 https://epubs.siam.org/doi/book/10.1137/1.9780898719918