TY - GEN
T1 - Simple parallel and distributed algorithms for spectral graph sparsification
AU - Koutis, Ioannis
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling. Leveraging the algorithms of Baswana and Sen for computing spanners, we obtain the first distributed spectral sparsification algorithm. We also obtain a parallel algorithm with improved work and time guarantees. Combining this algorithm with the parallel framework of Peng and Spielman for solving symmetric diagonally dominant linear systems, we get a parallel solver which is much closer to being practical and significantly more efficient in terms of the total work.
AB - We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling. Leveraging the algorithms of Baswana and Sen for computing spanners, we obtain the first distributed spectral sparsification algorithm. We also obtain a parallel algorithm with improved work and time guarantees. Combining this algorithm with the parallel framework of Peng and Spielman for solving symmetric diagonally dominant linear systems, we get a parallel solver which is much closer to being practical and significantly more efficient in terms of the total work.
KW - Distributed algorithms
KW - Parallel algorithms
KW - SDD linear systems
KW - Spectral sparsification
UR - http://www.scopus.com/inward/record.url?scp=84904466971&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904466971&partnerID=8YFLogxK
U2 - 10.1145/2612669.2612676
DO - 10.1145/2612669.2612676
M3 - Conference contribution
AN - SCOPUS:84904466971
SN - 9781450328210
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 61
EP - 66
BT - SPAA 2014 - Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
T2 - 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2014
Y2 - 23 June 2014 through 25 June 2014
ER -