Scalable Algorithmic Primitives for Data Science
summary
Argues that solving graph-structured linear systems becomes practical by combining preconditioning, randomized row sampling and combinatorial sparsifiers: claims graph Laplacian systems admit nearly-linear solvers (theory like m log^{O(1)} n, later improved toward m sqrt(log n) bounds) using ultrasparsification and elimination-based preconditioners. Reports working implementations (Laplacian.jl and combinatorial multigrid) that handle ~10^7–10^8 edges in ~20s, versus sorting at ~10^9 items; notes interior‑point iterations can blow up condition numbers around iteration 25–30 and that hybrid PCG+incomplete Cholesky gives ~10–20× practical gains.
AI-written summary · about
chapters (20)
- 0:00Introduction
- 0:51Motivation
- 2:03Primitives
- 3:10Linear System as a Primitive
- 10:15Linear System Solving
- 10:45Open Question
- 12:51Direct Method
- 13:47Backslash
- 17:39Nonzeros Graph
- 20:08Hybrid Algorithms
- 23:03Graph Laplacians
- 26:27Ultras and Elimination
- 28:40Sampling from Large matrices
- 30:59Edge Vertex Incidence Matrix
- 34:35Linear Elasticity
- 35:21Direct Graphs
- 35:44Future Directions
- 36:31Graph Laplacian
- 38:14Internal Graph Structure
- 40:00Truss Hardness
related talks
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
29mImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments
51mNearly Linear Time Algorithms for Solving Inverse Symmetric M-Matrices
01h 03mSketching as a Tool for Numerical Linear Algebra
49mGraph Based Processing of Big Images
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
09mOn the Power of Preconditioning in Sparse Linear Regression
30mScalable Graph-Parallel Inference Algorithms and Systems