TY - GEN

T1 - Near 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

PY - 2011

Y1 - 2011

N2 - 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 logO(1) n log 1/ε work and O(m1/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.

AB - 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 logO(1) n log 1/ε work and O(m1/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.

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=79959665275&partnerID=8YFLogxK

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

U2 - 10.1145/1989493.1989496

DO - 10.1145/1989493.1989496

M3 - Conference contribution

AN - SCOPUS:79959665275

SN - 9781450307437

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 13

EP - 22

BT - SPAA'11 - Proceedings of the 23rd Annual Symposium on Parallelism in Algorithms and Architectures

T2 - 23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11

Y2 - 4 June 2011 through 6 June 2011

ER -