Graph BLAS Forum
Goals and premises
The Graph BLAS Forum is an open effort to define standard building blocks for graph algorithms in the language of linear algebra.
We believe that the state of the art in constructing a large collection of graph algorithms in terms of linear algebraic operations is mature enough to support the emergence of a standard set of primitive building blocks. We believe that it is critical to move quickly and define such a standard, thereby freeing up researchers to innovate and diversify at the level of higher level algorithms and graph analytics applications. This effort was inspired by the Basic Linear Algebra Subprograms (BLAS) of dense Linear Algebra, and hence our working name for this standard is “the Graph BLAS”.
A key insight behind this work is that when a graph is represented by a sparse incidence or adjacency matrix, sparse matrix-vector multiplication is a step of breadth first search. By generalizing the pair of scalar operations involved in the linear algebra computations to define a semiring, we can extend the range of these primitives to support a wide range of parallel graph algorithms.
Our 2013 manifesto for this project can be found here.
The mathematical definition of the Graph BLAS can be found here.
Background information about graphs in the language of linear algebra can be found in the book: Graph Algorithms in the Language of Linear Algebra, edited by J. Kepner and J. Gilbert, SIAM, 2011.
A straw man proposal for the Graph BLAS can be found here.
Contribute a paper on any aspect of building blocks for graph algorithms to the Graph Algorithms Building Blocks workshop at IPDPS 2017.
Application Program Interface (API)
The C language API development is in the final stages, pursued by the following group (alphabetical): Aydın Buluç, Tim Mattson, Scott McMillan, José Moreira, Carl Yang
Version 0.9.1 of the C language specification can be downloaded from here.
This document is a preliminary draft of the GraphBLAS C standard. It includes text from the specification up to and including the matrix multiply operation GrB mxm(). We plan to follow the template established by GrB mxm() as we document the other GraphBLAS operations. Timely feedback on GrB mxm() is therefore critical; hence why we’ve released this preliminary version of the document.
GraphBLAS mailing list
If you wish to join our effort (or just watch it), please send an email message to our mailing list coordinator.
Workshops and conferences featuring the Graph BLAS (reverse chronological)
- GraphChallenge 2017: Submission deadline summer 2017
- HPEC 2017: Submission deadline May 19, 2017
- GABB 2017 @IPDPS: Submission deadline January 31, 2017
Projects developing implementations of the Graph BLAS
Steering Committee (alphabetical)
- David Bader (Georgia Tech)
- Jeremy Kepner (MIT Lincoln Labs)
- Tim Mattson (Intel)
- Henning Meyerhenke (KIT)