From Sparse Matrices to Graphs and Back Again
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Argument claims sparse matrix and graph work are reciprocal: decades of graph methods optimize sparse Cholesky via nested dissection and chordal completion, while recent progress brings graph kernels into linear-algebra primitives. Concrete numbers: dense benchmark reaches 33.3 PFLOPS (Top500) while Graph500 tops at 15.3 gigaTEPS, a 2,000× ratio that shrinks from 400,000× three years earlier thanks mostly to algorithms and software. Practical details include semiring sparse matrix primitives, avoiding explicit A^T A, and an emerging GraphBLAS forum to standardize APIs.
AI-written summary · about
chapters (4)
- 0:00Graph and matrix connection
- 22:32Performance and benchmarking
- 24:05Graph algorithms as linear
- 27:47Standardizing graph BLAS
related talks
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
47mMultiscale Analysis on and of Graphs
01h 05mGraph Algorithms in the MPC Model
01h 37mGraphons and Graph Limits 3
39mThorny path to the Large Scale Graph Processing
59mHardness for Graph Problems - Reductions Based on APSP and SETH
39mThorny path to the Large Scale Graph Processing
23mScaph: Scalable GPU-Accelerated Graph Processing with Value-Driven Differential...