Graph algorithms in the language of linear algebra

What Hacker News says

1. lukburchardJul 2023
   There is a book I would like to recommend, as it was not mentioned. The book "Graph algorithms in the language of linear algebra"[1] gives an overview and intuition of different graph algorithms expressed in linear algebra using semirings. The concept of expressing graphs as adjacency matrices (or incidence matrices) is quite old and was already noted by Koenig[4][5]. I remember the duality was used in some proofs and algorithms while doing my CS degree, e.g., see the Floyd–Warshall algorithm. One advantage of using linear algebra, apart from the beauty of it, is that naturally, vectorization and parallelization strategies become easier to implement. In practice, sparse linear algebra is used to reduce space and computational complexity. This is done by storing the matrices in compressed formats, such as COO/CSR/ELLPack.

   In HPC, there are multiple frameworks to do distributed sparse linear algebra, and also more graph and GPU focussed frameworks using semirings as the abstraction layer (CombBLAS[2], GraphBLAST[3]).

   References:

   [1] Kepner, Jeremy, and John Gilbert, eds. Graph algorithms in the language of linear algebra. Society for Industrial and Applied Mathematics, 2011.

   [2] Buluç, Aydın, and John R. Gilbert. "The Combinatorial BLAS: Design, implementation, and applications." The International Journal of High Performance Computing Applications 25.4 (2011): 496-509.

   [3] Yang, Carl, Aydın Buluç, and John D. Owens. "GraphBLAST: A high-performance linear algebra-based graph framework on the GPU." ACM Transactions on Mathematical Software (TOMS) 48.1 (2022): 1-51.

   [4] D. Konig. Graphen und Matrizen (Graphs and matrices). Matematikai Lapok, 38:116–119, 1931.

   [5] D. Konig. Theorie der endlichen und unendlichen graphen (Theory of Finite and Infinite Graphs). Leipzig: Akademie Verlag M.B.H. 1936.

   Show morethread
2. faizshahFeb 2022
   Related: There’s a really good book called “Graph Algorithms in the Language of Linear Algebra” if you’re interested in GRAPHBLAS related topics.
   thread
3. JadeNBMay 2020
   Graph algorithms in the language of linear algebra: https://epubs.siam.org/doi/book/10.1137/1.9780898719918 .
   thread
4. espeedApr 2019
   Hi Michel - You're working on a GraphBLAS Postgres implementation [0] -- here's an open question I've been pondering...

   [0] Postgres GraphBLAS https://github.com/michelp/pggraphblas

   Now that we have SOTA linear algebra models for graphs [1], logic [2] and the lambda calculus [3] that are being optimized for vectorized parallel compute on modern CPU/GPU/TPUs -- do we have the makings for a unified linear algebra model that obsoletes the relational algebra model in relational DBs?

   [1] Graph Algorithms in the Language of Linear Algebra (2011) https://epubs.siam.org/doi/book/10.1137/1.9780898719918

   Mathematical Foundations of the GraphBLAS (2016) https://arxiv.org/pdf/1606.05790.pdf

   [2] A Linear Algebraic Approach to Datalog Evaluation (2017) [pdf] https://arxiv.org/abs/1608.00139

   A Linear Algebraic Approach to Logic Programming (2018) https://www.imperial.ac.uk/media/imperial-college/faculty-of...

   [3] Lineal: A linear-algebraic Lambda-calculus (2017) https://arxiv.org/pdf/quant-ph/0612199.pdf

   The Vectorial λ-Calculus (2017) https://arxiv.org/pdf/1308.1138.pdf

   Simple λΠ-interpreter for matrix computation (2017) http://cs242.stanford.edu/assets/projects/2017/nykh.pdf

   Algebra and the Lambda Calculus https://people.csail.mit.edu/jaffer/lambda.txt

   Show morethread
5. espeedJan 2019
   Yes, 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

   Show morethread
6. espeedOct 2018
   My burgeoning conjecture (as hinted at in a previous comment) is that all can be unified, transformed, and optimized for modern hardware under the matrix model of computation -- type theory, the lambda calculus, the actor model, neural nets, graph computing -- I'm starting to see a path to where all models are aligned across vectors of unity.

   Here are some the correspondences I've been looking at...

   * Graph algos in the lang of linear algebra now realized and encoded into GraphBLAS [1]

   * The three normed division algebras are unified under a complex Hilbert space [2]

   * Ascent sequences and the bijections discovered between four classes of combinatorial objects [3]

   * Dependent Types and Homotopy Type Theory [4]

   * Bruhat–Tits buildings, symmetry, and spatial decomposition [5]

   * Distributed lattices, topological encodings, and succinct representations [6]

   * Zonotopes and Matroids and Minkowski Sums [7]

   * Holographic associative memory and entanglement renormalization [8]

   [1] Graph Algorithms in the Language of Linear Algebra (Jeremy Kepner) http://www.mit.edu/~kepner/ Discussion: https://news.ycombinator.com/item?id=18099520

   [2] Division Algebras and Quantum Theory (John Baez) http://math.ucr.edu/home/baez/rch.pdf

   [3] (2 + 2)-free posets, ascent sequences and pattern avoiding permutations [pdf] https://www.sciencedirect.com/science/article/pii/S009731650...

   [4] Cartesian Cubical Computational Type Theory: Constructive Reasoning with Paths and Equalities [pdf] https://www.cs.cmu.edu/~rwh/papers/cartesian/paper.pdf

   [5] Bruhat–Tits buildings and p-adic Lie groups https://en.wikipedia.org/wiki/Building_(mathematics)

   [6] Distributive lattices and Stone-space dualities https://en.wikipedia.org/wiki/Distributive_lattice#Represent...

   [7] Solving Low-Dimensional Optimization Problems via Zonotope Vertex Enumeration [video] https://www.youtube.com/watch?v=NH_CpMYe3tw https://en.wikipedia.org/wiki/Zonohedron

   [8] Entanglement Renormalization (G Vidal) https://authors.library.caltech.edu/9242/1/VIDprl07.pdf?hovn... Holography https://en.wikipedia.org/wiki/Holographic_associative_memory

   Google Scholar: https://scholar.google.com/scholar?q=related:Yi-GtarGxh0J:sc...

   Show morethread