Parallelism in modern sparse solvers
summary
Claims concrete speedups and workable tradeoffs: reordering is now ~25% of runtime so approximate minimum degree (AMD) with a relaxed MIS-2 selection and 10–20% degree slack gives up to ~8× speedups over SuiteSparse on many matrices and increases parallelism by an order of magnitude; nested dissection shortens elimination-tree height but costs expensive partitioning; symbolic elimination tree predicts fill; heavy‑weight distributed perfect‑matching (short augmenting paths) scales to thousands of cores and yields near‑optimal diagonals; GPU work uses sparsity‑aware SpGEMM and persistent kernels and outperforms cuSPARSE IC on several inputs.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:13Sparsity and its history
- 6:12Sparse linear systems
- 12:00Sparse Cholesky basics
- 17:25Elimination tree role
- 22:52Reordering to minimize fill
- 26:03Parallelism in minimum degree
- 31:28Nested dissection vs minimum degree
- 36:10Parallel triangular solves
- 41:08Multifrontal methods and supernodes
- 44:04Non-symmetric pivoting challenges
- 49:53Direct solve limitations
- 51:03Iterative solvers and Krylov methods
- 54:32Preconditioners and parallelism
- 59:29Random spanning tree preconditioners
- 1:03:06Multigrid basics
- 1:05:56Parallel sparse matrix multiplication in AMG
- 1:08:09Q&A
related talks
01h 05mThink Parallel
39mThe best multicore-parallelization refactoring you've never heard of
01h 27mKeynote: Multidimensional Parallel Standard C++
23mParallel Sequences in Multicore OCaml
43mParallel Algorithms: Work Smarter, Not Harder
01h 02mInside Visual C++' Parallel Algorithms
20mTruly Stateless, Optimal Dynamic Partial Order Reduction
56mBlock-Based Parallel Programming