4 ms·
This interview with Tim Davis has a bit of background information. https://www.acm.org/articles/people-of-acm/2019/tim-davis https://www.acm.org/articles/peopl
by FabHK 6y ago
This interview with Tim Davis has a bit of background information.
https://www.acm.org/articles/people-of-acm/2019/tim-davis https://www.acm.org/articles/people-of-acm/2019/tim-davis
> I picked Gaussian elimination. "That will be quick," I thought. Not! I got started on matrices in 1985 and I'm not done with Gaussian elimination yet.
> GraphBLAS is a community effort, including industry, academics, and government labs, that is working to design a library that can implement graph algorithms based on sparse linear algebra over semirings. There are lots of great graph libraries out there that don't exploit the linear algebraic abstraction, but most of what they do can be viewed as matrix operations on adjacency matrices. GraphBLAS makes the connection to linear algebra explicit.
> GraphBLAS gives the graph algorithm developer the power and abstraction of linear algebra, with all its advantages (associative and distributive laws, AB=(B'A')', and so on). One level of breadth-first search, for example, is a single sparse matrix-times-sparse vector multiply, with no loss of asymptotic efficiency. Google's entire PageRank computation can be done with a handful of iterations around a single call to GraphBLAS, using what I call the "PageRank semiring."
- chrisaycock 6y ago>> Google's entire PageRank computation can be done with a handful of iterations around a single call to GraphBLAS, using what I call the "PageRank semiring." The author has an example of PageRank in C: https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable/Demo/Source/dpagerank.c https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable... I assume his "single call" statement refers to the MATLAB version: https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable/Demo/MATLAB/dpagerank.m https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable... for i = 1:20 r = ((c*r) * C) + a * sum (r) ; end The MATLAB interface uses overloaded operators and methods on a GraphBLAS matrix object.
- DocSparse 6y agoI was referring to the PageRank_semiring in https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/5e569f2fcb0597b4ad3c60fca1a4ff8e938fd111/Demo/Source/dpagerank2.c#L348 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.
- michelpp 6y agoHere are two different PageRank approaches with pygraphblas: https://github.com/michelp/pygraphblas/blob/master/pygraphblas/demo/PageRank.ipynb https://github.com/michelp/pygraphblas/blob/master/pygraphbl...
- weswpg 6y ago> AB=(B'A')' Can someone clarify the notation for me? What is B' and A'? I've never seen that before.
- soedirgo 6y agoIt's the transpose operation [1]. See property 3. [1] https://en.wikipedia.org/wiki/Transpose https://en.wikipedia.org/wiki/Transpose