pygraphblas

This is interesting to me because it's advancing the work on the notion of quantum graph problem solving. I'm sure we've all heard how quantum computers can be used in the future to decrypt information from today. There's a lot of research out there on how QC may be able to efficiently factor large semiprimes and bust our existing cryptographic algorithms, but to me this is the more mundane side of QC. The exciting side to me is that many graph problems, particularly whole graph problems like connectivity and shortest paths have a potential quantum advantage. This is particularly advantageous for sparse and hypersparse graphs that have billions of nodes but relatively low node degree. Language Models, chemical assay databases, proteomics, causal inference, and fraud detection are just a few problems that involve huge sparse graphs that

Yes, multiplying graph adjacency matrices over a min-tropical semiring produces shortest paths. APL supports this syntactically, but how does it function in the real world? What if the matrices are extremely sparse, like almost all real world graphs are? Syntax is the easy the problem. The hard problem is having very sparse graphs with billions of nodes and many billions of edges. How is a square matrix going to deal with that? Sparse and hypersparse graph computing is hard, which is not syntactically relevant. Python does not have this terse a syntax, but it gets very close with multiple bindings to the SuiteSparse GraphBLAS Hypersparse graph processing libraries, which intrinsically supports sparse graphs and a very large number of operators, including the tropical min/max ones. Suitesparse doesn't provide syntax (that's the easy

There is a logarithmic semiring: https://en.wikipedia.org/wiki/Log_semiring which can be used to multiply two sparse matrices with the GraphBLAS. here is an example in Python: https://github.com/Graphegon/pygraphblas/blob/main/demo/Log-...

Using Linear Algebra to solve Graph problems, in particular, algebra over Tropical Semirings. Here's a great, but not graph specific, introduction to the advanced math behind the subject by Madeline Brandt: https://www.youtube.com/watch?v=S_bVv7Lau-s There is an open source effort to bring this style of mathematical analysis to graph optimization problems (shortest path, resource scheduling, etc) called the GraphBLAS: https://graphblas.github.io/ I am the author of the pygraphblas Python binding around the GraphBLAS library, you can find a lot of examples in the demo notebooks shown in the README: https://github.com/Graphegon/pygraphblas

Python wrapper around The GraphBLAS API: https://github.com/michelp/pygraphblas For an upcoming paper we've open sourced using pygraphblas to analyse the bitcoin graph using the GAP benchmarks on a server with 1TB of RAM: https://github.com/Graphegon/CoinBLAS

> They can absolutely have meanings assigned outside the usual "when multiplied by a vector" type of calculations. For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. Not disputing your basic point, but I'm not sure "very often never" is entirely accurate. In the GraphBLAS API vector/matrix and matrix/vector multiplication is key for almost all algorithms that depend on breadth first search, this is because matrix/vector multiplication is a single step in a BFS which is the core operation of the GraphBLAS. The vector is typically used to hold the current frontier (and mask). See the "Shortest Path Lengths" example here: https://github.com/michelp/pygraphblas/blob/master/pygraphbl... (disclosure, I am the pygraphblas author). > Purist test: aren'

Numba is indeed a great library for speeding up Python and also doing other useful things when interacting when external libraries. For example the "jit compile a single function" feature is gold when you need to pass a function callback pointer into a C library. This is how pygraphblas compiles Python functions into semiring operators that are then passed to the library which has no idea that the pointer is to jit compiled python function: https://github.com/michelp/pygraphblas/blob/master/tests/tes...

SuiteSparse doesn't support GPUs just yet, but when it does, you can do this with pygraphblas: https://github.com/michelp/pygraphblas (I am the pygraphblas author)

It's so early in this work that you might be the first person asking those specific questions. I'm no expert but I take it by VLSI you mean doing circuit routing and simulation and optimizing that topology. My gut tells me those would be good fits for the GraphBLAS. If the base types don't suit your needs, you can always make your own. Tim Davis has talked about how he's made new types that are small nxn matrices as elements of a larger matrix. You can have complex, quaternion, or complex bags of stuff as matrix elements as long as you define the operators you need to work on those types. Here's an example of using User Defined Types for a shortest path algorithm that also stores backlinks along the shortest path so the shortest path tree is materialized. in Python: https://github.com/michelp/pygraphblas/blob/master/pygraphbl...

There is also a Python wrapper: https://github.com/michelp/pygraphblas

Here are two different PageRank approaches with pygraphblas: https://github.com/michelp/pygraphblas/blob/master/pygraphbl...

pygraphblas author here, here is a good notebook introduction to the very basics of GraphBLAS with Python. The concepts carry naturally to the C API as well: https://github.com/michelp/pygraphblas/blob/master/pygraphbl... I also made a quick introduction video for a paper submission you can see here: https://www.youtube.com/watch?v=JUbXW_f03W0