2011/11/07 by Blelloch, Guy E., Gupta, Anupam, Koutis, Ioannis +3 · 1 citation
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1111.1750
We present the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input of a SDD n-by-n matrix A with m non-zero entries and a vector b, our algorithm computes a vector x such that \norm[A]x - A+b ≤ \vareps ⋅ \norm[A]A+b in O(mlogO(1)nlog\frac1ε) work and O(m1/3+θlog \frac1ε) 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 \otilde(|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(n1+α) work and O(nα) depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in \otilde(|E|) work and polylogarithmic depth. We apply this subgraph construction to derive a parallel linear system solver. By using this solver in known applications, our results imply improved parallel randomized algorithms for several problems, including single-source shortest paths, maximum flow, minimum-cost flow, and approximate maximum flow.