Mathematical foundations of the GraphBLAS
Mathematical foundations of the GraphBLAS
复制标题
DOI：
10.1109/hpec.2016.7761646
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
J. Kepner;Peter Aaltonen;David A. Bader;A. Buluç;F. Franchetti;J. Gilbert;D. Hutchison;Manoj Kumar;A. Lumsdaine;Henning Meyerhenke;Scott McMillan;Carl Yang;John Douglas Owens;Marcin Zalewski;T. Mattson;J. Moreira
中科院分区：
文献类型：
--
作者：
J. Kepner;Peter Aaltonen;David A. Bader;A. Buluç;F. Franchetti;J. Gilbert;D. Hutchison;Manoj Kumar;A. Lumsdaine;Henning Meyerhenke;Scott McMillan;Carl Yang;John Douglas Owens;Marcin Zalewski;T. Mattson;J. Moreira
GraphBLAS标准（GraphBlas.org）正在开发中，旨在将基于矩阵的图形算法的潜力带给尽可能广泛的受众。在数学上，GraphBLAS定义了一组核心的基于矩阵的图形操作，可用于在各种编程环境中实现各种图形算法。本文介绍了GraphBLAS的数学。图表示顶点与边之间的连接。矩阵可以使用邻接矩阵或关联矩阵来表示各种各样的图。邻接矩阵通常更容易分析，而关联矩阵通常更适合表示数据。幸运的是，这两者很容易通过矩阵乘法连接起来。矩阵数学的一个关键特征是，非常少量的矩阵运算可以用来处理非常广泛的图形。这种少量操作的可组合性是GraphBLAS的基础。像GraphBLAS这样的标准只有在性能开销低的情况下才有效。原型GraphBLAS实现的性能测量表明，开销很低。
The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix-based graph algorithms to the broadest possible audience. Mathematically, the GraphBLAS 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 multiplication. 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 a 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.