TY - JOUR

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

AU - Blelloch, Guy E.

AU - Gupta, Anupam

AU - Koutis, Ioannis

AU - Miller, Gary L.

AU - Peng, Richard

AU - Tangwongsan, Kanat

N1 - Funding Information:
Acknowledgements This work is partially supported by the National Science Foundation under grant numbers CCF-1018463, CCF-1018188, and CCF-1016799, CCF-1149048, by an Alfred P. Sloan Fellowship, and by generous gifts from IBM, Intel, and Microsoft.

PY - 2014/10

Y1 - 2014/10

N2 - 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 x̃ such that (Formula Persented) work and (Formula Persented) depth for any θ>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(mlogO(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 α) in O(mlogO(1) n) work and O(n α) depth for any α>0. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in O(mlogO(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.

AB - 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 x̃ such that (Formula Persented) work and (Formula Persented) depth for any θ>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(mlogO(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 α) in O(mlogO(1) n) work and O(n α) depth for any α>0. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in O(mlogO(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.

KW - Linear systems

KW - Low-diameter decomposition

KW - Low-stretch spanning trees

KW - Low-stretch subgraphs

KW - Parallel algorithms

UR - http://www.scopus.com/inward/record.url?scp=84907600482&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84907600482&partnerID=8YFLogxK

U2 - 10.1007/s00224-013-9444-5

DO - 10.1007/s00224-013-9444-5

M3 - Article

AN - SCOPUS:84907600482

SN - 1432-4350

VL - 55

SP - 521

EP - 554

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 3

ER -