Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

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 ∥x̃ - A⁺ b∥_A ≤ ε · ∥ A⁺ b∥_A in O(m log^O(1) n log 1/ε work and O(m^1/3+θ log 1/ε depth for any fixed θ > 0. The algorithm relies on a parallel algorithm for generating low-stretch spanning trees or spanning subgraphs. To this end, we first develop a parallel decomposition algorithm that in polylogarithmic depth and Õ(|E|) work, partitions a graph into components with polylogarithmic diameter such that only a small fraction of the original edges are between the components. This can be used to generate low-stretch spanning trees with average stretch O(n^α) in O(n ^1+α) work and O(n^α) depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in O(|E|) work and polylogarithmic depth. We apply this subgraph construction to derive our solver. By using the linear system solver in known applications, our results imply improved parallel randomized algorithms for several problems, including single-source shortest paths, maximum flow, min-cost flow, and approximate max-flow.