Randomized Asynchronous Linear Solvers
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Proposes a randomized Gauss‑Seidel solver for large sparse symmetric positive definite systems that runs fully asynchronously on shared memory with atomic updates and a damped step size β. Gives a provable expected linear convergence rate governed by trace/min eigenvalue (≈n·κ) with extra slowdown depending on asynchrony parameter τ, and shows on a social‑media regression matrix that 10 iterations reach residual ≈1e-3 while 64 threads deliver about 48× speedup and acceptable accuracy.
AI-written summary · about
chapters (12)
- 0:00Start
- 0:33Motivation 1
- 3:15Motivation 2: A Well-Known Trend
- 4:00Asynchronous Numerical Methods
- 4:41Traditional Approach
- 5:42Recent Work
- 7:11Simple (almost obvious) Iteration
- 11:46Randomized Gauss-Seidel (pseudo-code)
- 12:25Shared Memory Asynchronous Randomized Gauss-Seidel
- 19:37Without Occasional Synchronization
- 21:05Some Experimental Results
- 23:02Conclusions
related talks
17mZEN: Empowering Distributed Training with Sparsity-driven Data Synchronization
21mMassive proofs for the masses
16mSDE Approximations and Scaling Rules for Distributed Deep Learning
16mDi-PS: System-Algorithm Co-Design for Asynchronous and Heterogeneous Cross-cluster...
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
01h 07mThe Asynchronous C++ Parallel Programming Model
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
23mRandomized Testing of Distributed Systems with Probabilistic Guarantees