4 ms·

How do these dense linear algebra oriented implementations differ with stack-oriented algorithms, like in https://github.com/chen0040/lua-graph https://github.c

How do these dense linear algebra oriented implementations differ with stack-oriented algorithms, like in https://github.com/chen0040/lua-graph https://github.com/chen0040/lua-graph ?

ctchocula 8y ago
Nitpick: The article talks about sparse linear algebra (rather than dense) by modeling a graph traversal as a sparse matrix-vector multiplication. The sparse matrix represents the adjacency matrix of the graph, and the vector represents the subset of vertices that are currently "active" (you can think of an active vertex as being in the workqueue for a breadth-first-search). I haven't tried benchmarking Prof. Davis's GraphBLAS implementation myself against the one you linked to. My intuition would be that the GraphBLAS one is faster for larger graphs, because it uses data structures like CSR (compressed sparse row) [1], which are heavily optimized for processing static graphs (i.e. graphs that are not very amenable to adding vertices or edges). Based on the code examples on the first page, lua-graph seems more focused on small, dynamic graphs where the user can easily add vertices and edges. Short answer: they target different sets of applications. GraphBLAS is faster for processing large, static graphs with |V| and |E| in the millions or billions. lua-graph perhaps more flexible and handles dynamic graphs. [1] https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format) https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_spars...
- DocSparse 8y ago
  GraphBLAS uses sparse matrices internally, and the API assumes a sparse format. The data structure is opaque, however, so if I want, I could use dense matrices if it's faster (and there are times when that's faster; see for example the vector v in the push/pull BFS in LAGraph, at https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_bfs_pushpull.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... ). However, I don't switch to dense matrices automatically yet. SuiteSparse:GraphBLAS does have a fast incremental update mechanism, but it's not (yet) as flexible as other approaches. But the beauty of GraphBLAS is that the data structure is entirely opaque to the user, so if a library implementor such as myself wants to plunk in an entire new one, then the user code that relies on GraphBLAS doesn't change. It would be possible, even, to use lua-graph internally (or anything else, license permitting), and then to select the fastest format for the problem at hand. Or, lua-graph (or any graph library) could be augmented to support a GraphBLAS API to its functionality. Currently, SuiteSparse:GraphBLAS has four matrix formats: CSR, CSC, hypersparse CSR, and hypersparse CSC. The CSR and CSC formats take O(|V|+|E|) space, and the hypersparse formats take O(|E|) space. Hypersparse matrices arise in some problems, and subgraphs are often hypersparse. In the future, I would like to add a CSB format as well. I select between standard and hypersparse formats automatically. The default is CSR and I don't pick CSC automatically. In some cases, it would make sense to hold the matrix in both CSR and CSC formats, simultaneously, thus allowing fast access to both the in- and out-adjacency lists at the same time (at the cost of double the memory). I don't do that yet, however.

How do these dense linear algebra oriented implementations differ with stack-oriented algorithms, like in https://github.com/chen0040/lua-graph https://github.com/chen0040/lua-graph ?

ctchocula 8y ago

Nitpick: The article talks about sparse linear algebra (rather than dense) by modeling a graph traversal as a sparse matrix-vector multiplication. The sparse matrix represents the adjacency matrix of the graph, and the vector represents the subset of vertices that are currently "active" (you can think of an active vertex as being in the workqueue for a breadth-first-search). I haven't tried benchmarking Prof. Davis's GraphBLAS implementation myself against the one you linked to. My intuition would be that the GraphBLAS one is faster for larger graphs, because it uses data structures like CSR (compressed sparse row) [1], which are heavily optimized for processing static graphs (i.e. graphs that are not very amenable to adding vertices or edges). Based on the code examples on the first page, lua-graph seems more focused on small, dynamic graphs where the user can easily add vertices and edges. Short answer: they target different sets of applications. GraphBLAS is faster for processing large, static graphs with |V| and |E| in the millions or billions. lua-graph perhaps more flexible and handles dynamic graphs. [1] https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format) https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_spars...

DocSparse 8y ago
GraphBLAS uses sparse matrices internally, and the API assumes a sparse format. The data structure is opaque, however, so if I want, I could use dense matrices if it's faster (and there are times when that's faster; see for example the vector v in the push/pull BFS in LAGraph, at https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_bfs_pushpull.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... ). However, I don't switch to dense matrices automatically yet. SuiteSparse:GraphBLAS does have a fast incremental update mechanism, but it's not (yet) as flexible as other approaches. But the beauty of GraphBLAS is that the data structure is entirely opaque to the user, so if a library implementor such as myself wants to plunk in an entire new one, then the user code that relies on GraphBLAS doesn't change. It would be possible, even, to use lua-graph internally (or anything else, license permitting), and then to select the fastest format for the problem at hand. Or, lua-graph (or any graph library) could be augmented to support a GraphBLAS API to its functionality. Currently, SuiteSparse:GraphBLAS has four matrix formats: CSR, CSC, hypersparse CSR, and hypersparse CSC. The CSR and CSC formats take O(|V|+|E|) space, and the hypersparse formats take O(|E|) space. Hypersparse matrices arise in some problems, and subgraphs are often hypersparse. In the future, I would like to add a CSB format as well. I select between standard and hypersparse formats automatically. The default is CSR and I don't pick CSC automatically. In some cases, it would make sense to hold the matrix in both CSR and CSC formats, simultaneously, thus allowing fast access to both the in- and out-adjacency lists at the same time (at the cost of double the memory). I don't do that yet, however.