Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs

作者：Blelloch Guy E; Gupta Anupam; Koutis Ioannis; Miller Gary L; Peng Richard^*; Tangwongsan Kanat

来源：Theory of Computing Systems, 2014, 55(3): 521-554.

DOI：10.1007/s00224-013-9444-5

• Parallel algorithms
• Linear systems
• Low-stretch spanning trees
• Low-stretch subgraphs
• Low-diameter decomposition

We present the design and analysis of a nearly-linear work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input an SDD n-by-n matrix A with m nonzero entries and a vector b, our algorithm computes a vector such that in work and depth for any theta > 0, where A (+) denotes the Moore-Penrose pseudoinverse of A.
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 O(mlog (O(1)) n) work and polylogarithmic depth, partitions a graph with n nodes and m edges 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 (alpha) ) in O(mlog (O(1)) n) work and O(n (alpha) ) depth for any alpha > 0. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in O(mlog (O(1)) n) work and polylogarithmic depth. We apply this subgraph construction to derive a parallel linear 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.

• 出版日期2014-10