SuiteSparseGraphBLAS.jl

A fast, general sparse linear algebra and graph computation package, based on SuiteSparse:GraphBLAS.

Installation

using Pkg
Pkg.add("SuiteSparseGraphBLAS")

Benchmarks

julia> using SuiteSparseGraphBLAS
# Standard arithmetic semiring (+, *) matrix multiplication
julia> s = sprand(Float64, 100000, 100000, 0.05);
julia> v = sprand(Float64, 100000, 1000, 0.1);
julia> @btime s * v
  157.211 s (8 allocations: 1.49 GiB)
julia> s = GBMatrix(s); v = GBMatrix(v);
# Single-threaded
julia> @btime s * v
  54.649 s (26 allocations: 1.49 GiB)
# 2 threads
julia> @btime s * v
  30.258 s (26 allocations: 1.50 GiB)
# 4 threads
julia> @btime s * v
  21.738 s (26 allocations: 1.54 GiB)

# Indexing
julia> s = sprand(Float64, 100000, 100000, 0.05);
julia> @btime s[1:10:end, end:-10:1]
  344.355 ms (11 allocations: 76.32 MiB)
julia> s = GBMatrix(s);
julia> @btime s[1:10:end, end:-10:1]
  81.750 ms (39 allocations: 152.49 MiB)

Citing SuiteSparse:GraphBLAS

If you use SuiteSparseGraphBLAS.jl in your research please cite the following three papers:

pdf:

    @article{10.1145/3322125,
    author = {Davis, Timothy A.},
    title = {Algorithm 1000: SuiteSparse:GraphBLAS: Graph Algorithms in the Language of Sparse Linear Algebra},
    year = {2019},
    issue_date = {December 2019},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    volume = {45},
    number = {4},
    issn = {0098-3500},
    url = {https://doi.org/10.1145/3322125},
    doi = {10.1145/3322125},
    journal = {ACM Trans. Math. Softw.},
    month = {dec},
    articleno = {44},
    numpages = {25},
    keywords = {GraphBLAS, Graph algorithms, sparse matrices}
    }

pdf:

    @article{GraphBLAS7,
  author = {Davis, Timothy A.},
  title = {Algorithm 10xx: SuiteSparse:GraphBLAS: Graph Algorithms in the Language of Sparse Linear Algebra},
  year = {2022},
  journal = {ACM Trans. Math. Softw.},
  month = {(under revision)},
  note={See GraphBLAS/Doc/toms_parallel_grb2.pdf},
  keywords = {GraphBLAS, Graph algorithms, sparse matrices}
}

pdf:

@INPROCEEDINGS{9622789,
author={Pelletier, Michel and Kimmerer, Will and Davis, Timothy A. and Mattson, Timothy G.},
booktitle={2021 IEEE High Performance Extreme Computing Conference (HPEC)},
title={The GraphBLAS in Julia and Python: the PageRank and Triangle Centralities},
year={2021},
pages={1-7},
doi={10.1109/HPEC49654.2021.9622789},
ISSN={2643-1971},
month={Sep.}
}

Acknowledgements

This work was funded as part of Google Summer of Code over 3 summers, 2 of which were for Abhinav Mehndiratta and the last of which was for William Kimmerer.

Original author: Abhinav Mehndiratta

SuiteSparse author: Tim Davis

Mentors: Viral B Shah, Miha Zgubic, Tim Davis

Current maintainer: William Kimmerer