HackerPapers

arXiv:1606.05790cs.MS

Mathematical Foundations of the GraphBLAS

Jeremy Kepner, Peter Aaltonen, David Bader, Aydın Buluc, Franz Franchetti, John Gilbert, Dylan Hutchison, Manoj Kumar, Andrew Lumsdaine, Henning Meyerhenke, Scott McMillan, Jose Moreira, John D. Owens, Carl Yang, Marcin Zalewski, Timothy Mattson

Abstract

The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix based graph algorithms to the broadest possible audience. Mathematically the Graph- BLAS defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the mathematics of the GraphBLAS. Graphs represent connections between vertices with edges. Matrices can represent a wide range of graphs using adjacency matrices or incidence matrices. Adjacency matrices are often easier to analyze while incidence matrices are often better for representing data. Fortunately, the two are easily connected by matrix mul- tiplication. A key feature of matrix mathematics is that a very small number of matrix operations can be used to manipulate a very wide range of graphs. This composability of small number of operations is the foundation of the GraphBLAS. A standard such as the GraphBLAS can only be effective if it has low performance overhead. Performance measurements of prototype GraphBLAS implementations indicate that the overhead is low.

arXiv comments
9 pages; 11 figures; accepted to IEEE High Performance Extreme Computing (HPEC) conference 2016. arXiv admin note: text overlap with arXiv:1504.01039
Journal reference
DOI
doi:10.1109/HPEC.2016.7761646
Subjects
cs.MSMathematical Software astro-ph.IMInstrumentation and Methods for Astrophysics cs.DCDistributed, Parallel, and Cluster Computing cs.DSData Structures and Algorithms

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Apr 2019 to Mar 2024.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. The "missing" graph datatype already exists. It was invented in the '70s 1 comment

    • When you consider that a graph and a matrix are isomorphic, doing vector matrix multiplication takes a vector with a set value, say row 4, and multiplies it by a matrix where row 4 has values present that represent edges to the nodes that are adjacent to it (ie "adjacency"…

      michelppView on HNParent context

  2. What is GraphBLAS? 1 comment

    • 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]…

      espeedView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.