Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary Lee Miller, Richard Peng, Kanat Tangwongsan · 2011
This paper presents the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input an SDD n-by-n matrix A with m non-zero entries and a vector b, our algorithm computes a vector x such that Ax - A+b ≤ ε • A+b in O(m logO(1) n log 1/ε) work and O(m1/3+θ log 1/ε) depth for any fixed θ > 0.