Empirical Complexity of Laplacian Solvers: A Discussion
summary
Theory gives nearly-linear solvers but implementations remain rough: a published code uses Steiner preconditioners plus multigrid-style layers, hand‑coded matvec, and shows 4x speedup on 8 cores for one parallelization effort. Condition numbers and combinatorial constructions still need tightening; recent combinatorial algorithms make some steps nearly‑linear and could lower supports. The code is used in data mining but is unoptimized, brittle, and needs better interfaces, matchmaking between theorists and HPC engineers, and more robust benchmarking on hard instances.
AI-written summary · about
chapters (5)
- 0:00Start
- 1:30Graphs and sparse matrix computation (philosophical digression)
- 2:42Graph algorithms in sparse matrix computation
- 3:55Combinatorial Laplacian algorithms (partial list)
- 5:31The Laplacian World Championships
related talks
18mPortfolio Solving for Dafny
15mvLLM: Easy, Fast, and Cheap LLM Serving for Everyone
42mSolving MLOps from First Principles
12mVertical Mobility: Inference from MVP to Trillion Parameters
29mCustomizing and Evaluating LLMs, an Ops Perspective
17mAdvancing Performance via a Systematic Application of Research and Industrial Best(…)
32mWhat the game industry taught me about performance
20mSelf-hosting AI LLMs - a beginners guide