More Web Proxy on the site http://driver.im/

research-article

Public Access

Algorithm 1000: SuiteSparse:GraphBLAS: Graph Algorithms in the Language of Sparse Linear Algebra

Author:

Timothy A. DavisAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 45, Issue 4

Article No.: 44, Pages 1 - 25

https://doi.org/10.1145/3322125

Published: 09 December 2019 Publication History

All formats PDF

Abstract

SuiteSparse:GraphBLAS is a full implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. GraphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. An overview of the GraphBLAS specification is given, followed by a description of the key features and performance of its implementation in the SuiteSparse:GraphBLAS package.

Supplementary Material

ZIP File (1000.zip)

Software for SuiteSparse:GraphBLAS: Graph Algorithms in the Language of Sparse Linear Algebra

Download
7.83 MB

References

[1]

M. J. Anderson, N. Sundaram, N. Satish, M. M. A. Patwary, T. L. Willke, and P. Dubey. 2016. GraphPad: Optimized graph primitives for parallel and distributed platforms. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS’16). 313--322.

[2]

A. Azad, A. Buluç, and J. Gilbert. 2015. Parallel triangle counting and enumeration using matrix algebra. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop. 804--811.

Digital Library

[3]

A. Buluç and J. R. Gilbert. 2008. On the representation and multiplication of hypersparse matrices. In 2008 IEEE International Symposium on Parallel and Distributed Processing. 1--11.

[4]

A. Buluç and J. R. Gilbert. 2011. The combinatorial BLAS: Design, implementation, and applications. The International J. High Perform. Comput. Appl. 25, 4 (2011), 496--509. arXiv:https://doi.org/10.1177/1094342011403516

Digital Library

[5]

A. Buluç, T. Mattson, S. McMillan, J. Moreira, and C. Yang. 2017. The GraphBLAS C API Specification. Technical Report. http://graphblas.org/.

[6]

P. Cailliau. 2018. Benchmarking RedisGraph 1.0. Retrieved on 08 Nov, 2019 from https://redislabs.com/blog/new-redisgraph-1-0-achieves-600x-faster-performance-graph-databases.

[7]

T. A. Davis. 2006. Direct Methods for Sparse Linear Systems. SIAM, Philadelphia, PA.

Digital Library

[8]

T. A. Davis. 2018. Graph algorithms via SuiteSparse:GraphBLAS: Triangle counting and K-truss. In 2018 IEEE High Performance Extreme Computing Conference (HPEC’18). (doi to appear; in the meantime, see http://faculty.cse.tamu.edu/davis/publications_files/Davis_HPEC18.pdf).

[9]

T. A. Davis and Y. Hu. 2011. The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1 (Dec. 2011), 1:1--1:25.

Digital Library

[10]

T. A. Davis, S. Rajamanickam, and W. M. Sid-Lakhdar. 2016. A survey of direct methods for sparse linear systems. Acta Numerica 25 (2016), 383--566.

[11]

K. Ekanadham, W. Horn, J. Jann, M. Kumar, J. Moreira, P. Pattnaik, M. Serrano, G. Tanase, and H. Yu. 2014. Graph Programming Interface: Rationale and Specification. Technical Report RC25508 (WAT1411-052). IBM Research Division, Thomas J. Watson Research Center, Yorktown Heights, NY.

[12]

J. R. Gilbert, C. Moler, and R. Schreiber. 1992. Sparse matrices in MATLAB: Design and implementation. SIAM J. Matrix Anal. Appl. 13, 1 (1992), 333--356.

Digital Library

[13]

F. G. Gustavson. 1978. Two fast algorithms for sparse matrices: Multiplication and permuted transposition. ACM Trans. Math. Softw. 4, 3 (1978), 250--269.

Digital Library

[14]

D. Hutchison, J. Kepner, V. Gadepally, and B. Howe. 2016. From NoSQL Accumulo to NewSQL Graphulo: Design and utility of graph algorithms inside a BigTable database. In 2016 IEEE High Performance Extreme Computing Conference (HPEC’16). 1--9.

[15]

J. Kepner. 2017. GraphBLAS Mathematics. Technical Report. MIT Lincoln Lab. http://www.mit.edu/&sim;kepner/GraphBLAS/GraphBLAS-Math-release.pdf

[16]

J. Kepner, P. Aaltonen, D. Bader, A. Buluç, F. Franchetti, J. Gilbert, D. Hutchison, M. Kumar, A. Lumsdaine, H. Meyerhenke, S. McMillan, C. Yang, J. D. Owens, M. Zalewski, T. Mattson, and J. Moreira. 2016. Mathematical foundations of the GraphBLAS. In 2016 IEEE High Performance Extreme Computing Conference (HPEC’16). 1--9.

[17]

J. Kepner, W. Arcand, W. Bergeron, N. Bliss, R. Bond, C. Byun, G. Condon, K. Gregson, M. Hubbell, J. Kurz, A. McCabe, P. Michaleas, A. Prout, A. Reuther, A. Rosa, and C. Yee. 2012. Dynamic distributed dimensional data model (D4M) database and computation system. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’12). 5349--5352.

[18]

J. Kepner and J. Gilbert. 2011. Graph Algorithms in the Language of Linear Algebra. SIAM, Philadelphia, PA.

[19]

J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.

[20]

M. Luby. 1986. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 4 (1986).

Digital Library

[21]

L. Page, S. Brin, R. Motwani, and T. Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report 1999-66. Stanford InfoLab. http://ilpubs.stanford.edu:8090/422/ Previous number = SIDL-WP-1999-0120.

[22]

N. Sundaram, N. Satish, M. M. A. Patwary, S. R. Dulloor, M. J. Anderson, S. G. Vadlamudi, D. Das, and P. Dubey. 2015. GraphMat: High performance graph analytics made productive. In Proceedings of VLDB 2015, Vol. 8. 1214--1225.

[23]

C. Yang, A. Buluç, and J. D. Owens. 2018. Design principles for sparse matrix multiplication on the GPU. In Euro-Par 2018: Parallel Processing, M. Aldinucci, L. Padovani, and M. Torquati (Eds.). Springer International Publishing, 672--687.

Cited By

Wheatman BDong XShen ZDhulipala LŁącki JPandey PXu H(2024)BYO: A Unified Framework for Benchmarking Large-Scale Graph ContainersProceedings of the VLDB Endowment10.14778/3665844.366585917:9(2307-2320)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665859
Besançon MDias Garcia JLegat BSharma A(2024)Flexible Differentiable Optimization via Model TransformationsINFORMS Journal on Computing10.1287/ijoc.2022.028336:2(456-478)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0283
Dangi PBai ZJuneja RWijerathne DMitra T(2024)ZeD: A Generalized Accelerator for Variably Sparse Matrix Computations in MLProceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques10.1145/3656019.3689905(246-257)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1145/3656019.3689905
Show More Cited By

Recommendations

Algorithm 1037: SuiteSparse:GraphBLAS: Parallel Graph Algorithms in the Language of Sparse Linear Algebra
SuiteSparse:GraphBLAS is a full parallel implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse ...
Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate

CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AA^T, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, ...
Algorithm 907: KLU, A Direct Sparse Solver for Circuit Simulation Problems

KLU is a software package for solving sparse unsymmetric linear systems of equations that arise in circuit simulation applications. It relies on a permutation to Block Triangular Form (BTF), several methods for finding a fill-reducing ordering (variants ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 45, Issue 4

December 2019

207 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3375544

Editors:
Zhaojun Bai
University of California at Davis, USA
,
Wolfgang Bangerth
Colorado State University, USA

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 December 2019

Accepted: 01 March 2019

Revised: 01 November 2018

Received: 01 June 2018

Published in TOMS Volume 45, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

MIT Lincoln Laboratory
Redis Labs
National Science Foundation
Intel
NVIDIA
IBM

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

95
Total Citations
View Citations
2,812
Total Downloads

Downloads (Last 12 months)629
Downloads (Last 6 weeks)113

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wheatman BDong XShen ZDhulipala LŁącki JPandey PXu H(2024)BYO: A Unified Framework for Benchmarking Large-Scale Graph ContainersProceedings of the VLDB Endowment10.14778/3665844.366585917:9(2307-2320)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665859
Besançon MDias Garcia JLegat BSharma A(2024)Flexible Differentiable Optimization via Model TransformationsINFORMS Journal on Computing10.1287/ijoc.2022.028336:2(456-478)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0283
Dangi PBai ZJuneja RWijerathne DMitra T(2024)ZeD: A Generalized Accelerator for Variably Sparse Matrix Computations in MLProceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques10.1145/3656019.3689905(246-257)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1145/3656019.3689905
Kang SJun SDe V(2024)Sting: Near-storage accelerator framework for scalable triangle counting and beyondProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3658265(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3658265
Roanec JRoanec MBalsamo SKnottenbelt WAbad CShang W(2024)Go-Network: a graph sampling library written in GoCompanion of the 15th ACM/SPEC International Conference on Performance Engineering10.1145/3629527.3652903(151-155)Online publication date: 7-May-2024
https://dl.acm.org/doi/10.1145/3629527.3652903
He THu SLai LLi DLi NLi XLiu LLuo XLyu BMeng KShen SSu LWang LXu JYu WZeng WZhang LZhang SZhou JZhou XZhu DBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)GraphScope Flex: LEGO-like Graph Computing StackCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3653383(386-399)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3653383
Ranawaka IHussain MBlock CGerogiannis GTorrellas JAzad A(2024)Distributed-Memory Parallel Algorithms for Sparse Matrix and Sparse Tall-and-Skinny Matrix MultiplicationProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.1109/SC41406.2024.00052(1-17)Online publication date: 17-Nov-2024
https://dl.acm.org/doi/10.1109/SC41406.2024.00052
Zhang YTsai PTseng H(2024)Sparsepipe: Sparse Inter-operator Dataflow Architecture with Cross-Iteration Reuse2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO61859.2024.00090(1201-1216)Online publication date: 2-Nov-2024
https://doi.org/10.1109/MICRO61859.2024.00090
Feng YLiu ZLeng JGuo MZhu Y(2024)Cicero: Addressing Algorithmic and Architectural Bottlenecks in Neural Rendering by Radiance Warping and Memory Optimizations2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00096(1293-1308)Online publication date: 29-Jun-2024
https://doi.org/10.1109/ISCA59077.2024.00096
Milner CJananthan HKepner JGadepally VJones MMichaleas PPatel RPisharody SWachman GPentland A(2024)Teaching Network Traffic Matrices in an Interactive Game Environment2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00097(459-467)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00097
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents