TY - JOUR
T1 - Faster spectral sparsification and numerical algorithms for SDD matrices
AU - Koutis, Ioannis
AU - Levin, Alex
AU - Peng, Richard
N1 - Publisher Copyright:
© 2015 ACM.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.
PY - 2015/12/1
Y1 - 2015/12/1
N2 - We study algorithms for spectral graph sparsification. The input is a graph G with n vertices and medges, and the output is a sparse graph G that approximates G in an algebraic sense. Concretely, for all vectors x and any ∈ > 0, the graph G satisfies (1-∈)xT LGx ≤ xTLGx ≤ (1 + ∈)xT LGx, where LG and LG are the Laplacians of G and G, respectively. The first contribution of this article applies to all existing sparsification algorithms that rely on solving solving linear systems on graph Laplacians. These algorithms are the fastest known to date. Specifically, we show that less precision is required in the solution of the linear systems, leading to speedups by an O(log n) factor. We also present faster sparsification algorithms for slightly dense graphs: -An O(mlog n) time algorithm that generates a sparsifier with O(nlog3 n/∈2) edges. -An O(mlog log n) time algorithm for graphs with more than nlog5 nlog log n edges. -An O(m) algorithm for graphs with more than nlog10 n edges. -An O(m) algorithm for unweighted graphs with more than nlog8 n edges. These bounds hold up to factors that are in O(poly(log log n)) and are conjectured to be removable.
AB - We study algorithms for spectral graph sparsification. The input is a graph G with n vertices and medges, and the output is a sparse graph G that approximates G in an algebraic sense. Concretely, for all vectors x and any ∈ > 0, the graph G satisfies (1-∈)xT LGx ≤ xTLGx ≤ (1 + ∈)xT LGx, where LG and LG are the Laplacians of G and G, respectively. The first contribution of this article applies to all existing sparsification algorithms that rely on solving solving linear systems on graph Laplacians. These algorithms are the fastest known to date. Specifically, we show that less precision is required in the solution of the linear systems, leading to speedups by an O(log n) factor. We also present faster sparsification algorithms for slightly dense graphs: -An O(mlog n) time algorithm that generates a sparsifier with O(nlog3 n/∈2) edges. -An O(mlog log n) time algorithm for graphs with more than nlog5 nlog log n edges. -An O(m) algorithm for graphs with more than nlog10 n edges. -An O(m) algorithm for unweighted graphs with more than nlog8 n edges. These bounds hold up to factors that are in O(poly(log log n)) and are conjectured to be removable.
KW - Spectral sparsification
KW - Symmetric diagonally dominant (SDD) matrices
UR - http://www.scopus.com/inward/record.url?scp=84954203759&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954203759&partnerID=8YFLogxK
U2 - 10.1145/2743021
DO - 10.1145/2743021
M3 - Article
AN - SCOPUS:84954203759
VL - 12
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
SN - 1549-6325
IS - 2
M1 - 17
ER -