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 <i>n</i>-by-<i>n</i> matrix <i>A</i> with <i>m</i> non-zero entries and a vector <i>b</i>, our algorithm computes a vector <i>x</i> such that <i>A</i><i>x</i> - <i>A</i><sup>+<i>b</i></sup> ≤ ε • <i>A</i><sup>+<i>b</i></sup> in <i>O</i>(<i>m</i> log<sup><i>O</i>(1)</sup> <i>n</i> log 1/ε) work and <i>O</i>(<i>m</i><sup>1/3+θ</sup> log 1/ε) depth for any fixed θ > 0.</p> <p>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 <i>O</i>(|<i>E</i>|) 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 <i>O</i>(<i>n</i><sup>α</sup>) in <i>O</i>(<i>n</i><sup>1+α</sup>) work and <i>O</i>(<i>n</i><sup>α</sup>) depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in <i>O</i>(|<i>E</i>|) work and polylogarithmic depth. We apply this subgraph construction to derive our solver.</p> <p>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.
%0 Conference Paper
%1 Blelloch:2011:NLP:1989493.1989496
%A Blelloch, Guy E.
%A Gupta, Anupam
%A Koutis, Ioannis
%A Miller, Gary L.
%A Peng, Richard
%A Tangwongsan, Kanat
%B Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures
%C New York, NY, USA
%D 2011
%I ACM
%K parallel sdd sparsification
%P 13--22
%R 10.1145/1989493.1989496
%T Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
%U http://doi.acm.org/10.1145/1989493.1989496
%X 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 <i>n</i>-by-<i>n</i> matrix <i>A</i> with <i>m</i> non-zero entries and a vector <i>b</i>, our algorithm computes a vector <i>x</i> such that <i>A</i><i>x</i> - <i>A</i><sup>+<i>b</i></sup> ≤ ε • <i>A</i><sup>+<i>b</i></sup> in <i>O</i>(<i>m</i> log<sup><i>O</i>(1)</sup> <i>n</i> log 1/ε) work and <i>O</i>(<i>m</i><sup>1/3+θ</sup> log 1/ε) depth for any fixed θ > 0.</p> <p>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 <i>O</i>(|<i>E</i>|) 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 <i>O</i>(<i>n</i><sup>α</sup>) in <i>O</i>(<i>n</i><sup>1+α</sup>) work and <i>O</i>(<i>n</i><sup>α</sup>) depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in <i>O</i>(|<i>E</i>|) work and polylogarithmic depth. We apply this subgraph construction to derive our solver.</p> <p>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.
%@ 978-1-4503-0743-7
@inproceedings{Blelloch:2011:NLP:1989493.1989496,
abstract = {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 <i>n</i>-by-<i>n</i> matrix <i>A</i> with <i>m</i> non-zero entries and a vector <i>b</i>, our algorithm computes a vector <i>x</i> such that <i>A</i><i>x</i> - <i>A</i><sup>+<i>b</i></sup> ≤ ε • <i>A</i><sup>+<i>b</i></sup> in <i>O</i>(<i>m</i> log<sup><i>O</i>(1)</sup> <i>n</i> log 1/ε) work and <i>O</i>(<i>m</i><sup>1/3+θ</sup> log 1/ε) depth for any fixed θ > 0.</p> <p>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 <i>O</i>(|<i>E</i>|) 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 <i>O</i>(<i>n</i><sup>α</sup>) in <i>O</i>(<i>n</i><sup>1+α</sup>) work and <i>O</i>(<i>n</i><sup>α</sup>) depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in <i>O</i>(|<i>E</i>|) work and polylogarithmic depth. We apply this subgraph construction to derive our solver.</p> <p>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.},
acmid = {1989496},
added-at = {2012-07-24T15:36:43.000+0200},
address = {New York, NY, USA},
author = {Blelloch, Guy E. and Gupta, Anupam and Koutis, Ioannis and Miller, Gary L. and Peng, Richard and Tangwongsan, Kanat},
biburl = {https://www.bibsonomy.org/bibtex/2217eb6d169a326d2d527a5b33d879712/ytyoun},
booktitle = {Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures},
doi = {10.1145/1989493.1989496},
interhash = {f2f51b62e842c55e1955836d5eed81d2},
intrahash = {217eb6d169a326d2d527a5b33d879712},
isbn = {978-1-4503-0743-7},
keywords = {parallel sdd sparsification},
location = {San Jose, California, USA},
numpages = {10},
pages = {13--22},
publisher = {ACM},
series = {SPAA '11},
timestamp = {2012-07-24T15:36:43.000+0200},
title = {Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs},
url = {http://doi.acm.org/10.1145/1989493.1989496},
year = 2011
}