Hacker Newsnew | past | comments | ask | show | jobs | submit | DocSparse's commentslogin

Give us time; we're still in the beginning stages of writing algorithms that use it. If you dig through LAGraph, you'll find lots of messy prototypes, as we experiment on various methods. Those are drafts, not polished results. Our most recent methods are polished, extremely simple, yet very fast:

https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo...

https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo...

https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... (that one has 6 algorithms inside)

https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo...

We're working on the GPU version, and all the built-in semirings very work nicely on the GPU. For user-defined semirings, we will need the user operators defined as strings containing C code. Then they can all be done on the GPU too.


I was referring to the PageRank_semiring in https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/5e569f... . I wasn't counting the test for the termination condition -- in the statement in my interview, I assumed the # of iterations could just be given. I would guess that's the case for the Google PageRank computation, since the graph doesn't change so much each month when they compute it, they probably know how many iterations they need.


No, it's not nonsense at all. GraphBLAS does rely on semirings on sparse matrices, so it does use linear matrix algebra. But it doesn't use or compute a kernel explicitly.

A kernel is a vector x so that Ax = 0. There are places where y<m> = Ax = 0 is useful to compute (m is a mask, like a bulk-if statement, where y(i) is modified only if m(i)=1). If x is a set of nodes then A'x is the set union of the neighbors of x (assuming A(i,j) is the edge (i,j), which is typical but not required). Then if x has no neighbors in the set m, then y = 0. I use this in the GraphBLAS implementation of Luby's independent set algorithm (in my Demo/ folder of SuiteSparse/GraphBLAS).

There are lots of connections between linear algebra and graph theory. In this case, the idea of a kernel does find its place in a graph algorithm, but it's a special case. It's not something that appears everywhere in every graph algorithm.


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/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.


Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: