%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>^+<i>b</i> &#8804; &#949; &#8226; <i>A</i>^+<i>b</i> in <i>O</i>(<i>m</i> log^<i>O</i>(1) <i>n</i> log 1/&#949;) work and <i>O</i>(<i>m</i>^1/3+&#952; log 1/&#949;) depth for any fixed &#952; &#62; 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>^&#945;) in <i>O</i>(<i>n</i>^1+&#945;) work and <i>O</i>(<i>n</i>^&#945;) 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>^+<i>b</i> &#8804; &#949; &#8226; <i>A</i>^+<i>b</i> in <i>O</i>(<i>m</i> log^<i>O</i>(1) <i>n</i> log 1/&#949;) work and <i>O</i>(<i>m</i>^1/3+&#952; log 1/&#949;) depth for any fixed &#952; &#62; 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>^&#945;) in <i>O</i>(<i>n</i>^1+&#945;) work and <i>O</i>(<i>n</i>^&#945;) 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 }