4 ms·

Sorry if this is nonsense, are these semirings a form of "Kernel (linear algebra)"? They seem superficially similar at least, a normalized matrix which can serv

Sorry if this is nonsense, are these semirings a form of "Kernel (linear algebra)"? They seem superficially similar at least, a normalized matrix which can serve as an operation applied stepwise to a larger dataset.

michelpp 7y ago
Here are are a couple good introductions to semirings: https://www.youtube.com/watch?v=Gd_VT_Nj8Xw https://www.youtube.com/watch?v=Gd_VT_Nj8Xw https://www.youtube.com/watch?v=dluPFbuq6zs https://www.youtube.com/watch?v=dluPFbuq6zs Dr. Jeremy Kepner's paper is a good follow up read after those two quick videos: http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release.pdf http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release....
- espeed 7y ago
  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 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 https://epubs.siam.org/doi/book/10.1137/1.9780898719918 Mathematical Foundations of the GraphBLAS (2016) https://arxiv.org/pdf/1606.05790.pdf https://arxiv.org/pdf/1606.05790.pdf [2] A Linear Algebraic Approach to Datalog Evaluation (2017) [pdf] https://arxiv.org/abs/1608.00139 https://arxiv.org/abs/1608.00139 A Linear Algebraic Approach to Logic Programming (2018) https://www.imperial.ac.uk/media/imperial-college/faculty-of-engineering/computing/public/1718-pg-projects/AspisY-Logical-Abduction-via-Linear-Algebraic-Methods.pdf 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 https://arxiv.org/pdf/quant-ph/0612199.pdf The Vectorial λ-Calculus (2017) https://arxiv.org/pdf/1308.1138.pdf https://arxiv.org/pdf/1308.1138.pdf Simple λΠ-interpreter for matrix computation (2017) http://cs242.stanford.edu/assets/projects/2017/nykh.pdf http://cs242.stanford.edu/assets/projects/2017/nykh.pdf Algebra and the Lambda Calculus https://people.csail.mit.edu/jaffer/lambda.txt https://people.csail.mit.edu/jaffer/lambda.txt
DocSparse 7y ago
No, it's not nonsense at all. GraphBLAS does rely on semirings on sparse matrices, so it does use linear matrix algebra. But it doesn't use or compute a kernel explicitly. A kernel is a vector x so that Ax = 0. There are places where y<m> = Ax = 0 is useful to compute (m is a mask, like a bulk-if statement, where y(i) is modified only if m(i)=1). If x is a set of nodes then A'x is the set union of the neighbors of x (assuming A(i,j) is the edge (i,j), which is typical but not required). Then if x has no neighbors in the set m, then y = 0. I use this in the GraphBLAS implementation of Luby's independent set algorithm (in my Demo/ folder of SuiteSparse/GraphBLAS). There are lots of connections between linear algebra and graph theory. In this case, the idea of a kernel does find its place in a graph algorithm, but it's a special case. It's not something that appears everywhere in every graph algorithm.

michelpp 7y ago

Here are are a couple good introductions to semirings: https://www.youtube.com/watch?v=Gd_VT_Nj8Xw https://www.youtube.com/watch?v=Gd_VT_Nj8Xw https://www.youtube.com/watch?v=dluPFbuq6zs https://www.youtube.com/watch?v=dluPFbuq6zs Dr. Jeremy Kepner's paper is a good follow up read after those two quick videos: http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release.pdf http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release....

espeed 7y ago
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 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 https://epubs.siam.org/doi/book/10.1137/1.9780898719918 Mathematical Foundations of the GraphBLAS (2016) https://arxiv.org/pdf/1606.05790.pdf https://arxiv.org/pdf/1606.05790.pdf [2] A Linear Algebraic Approach to Datalog Evaluation (2017) [pdf] https://arxiv.org/abs/1608.00139 https://arxiv.org/abs/1608.00139 A Linear Algebraic Approach to Logic Programming (2018) https://www.imperial.ac.uk/media/imperial-college/faculty-of-engineering/computing/public/1718-pg-projects/AspisY-Logical-Abduction-via-Linear-Algebraic-Methods.pdf 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 https://arxiv.org/pdf/quant-ph/0612199.pdf The Vectorial λ-Calculus (2017) https://arxiv.org/pdf/1308.1138.pdf https://arxiv.org/pdf/1308.1138.pdf Simple λΠ-interpreter for matrix computation (2017) http://cs242.stanford.edu/assets/projects/2017/nykh.pdf http://cs242.stanford.edu/assets/projects/2017/nykh.pdf Algebra and the Lambda Calculus https://people.csail.mit.edu/jaffer/lambda.txt https://people.csail.mit.edu/jaffer/lambda.txt

DocSparse 7y ago

No, it's not nonsense at all. GraphBLAS does rely on semirings on sparse matrices, so it does use linear matrix algebra. But it doesn't use or compute a kernel explicitly. A kernel is a vector x so that Ax = 0. There are places where y<m> = Ax = 0 is useful to compute (m is a mask, like a bulk-if statement, where y(i) is modified only if m(i)=1). If x is a set of nodes then A'x is the set union of the neighbors of x (assuming A(i,j) is the edge (i,j), which is typical but not required). Then if x has no neighbors in the set m, then y = 0. I use this in the GraphBLAS implementation of Luby's independent set algorithm (in my Demo/ folder of SuiteSparse/GraphBLAS). There are lots of connections between linear algebra and graph theory. In this case, the idea of a kernel does find its place in a graph algorithm, but it's a special case. It's not something that appears everywhere in every graph algorithm.