TY - GEN

T1 - Improved spectral sparsification and numerical algorithms for SDD matrices

AU - Koutis, Ioannis

AU - Levin, Alex

AU - Peng, Richard

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

N2 - We present three spectral sparsification algorithms that, on input a graph G with n vertices and m edges, return a graph H with n vertices and O(n log n/e2) edges that provides a strong approximation of G. Namely, for all vectors x and any ε > 0, we have (1 - ε)xT L Gx ≤ x LHx ≤ (1 + ε)xT L Gx, where LG and LH are the Laplacians of the two graphs. The first algorithm is a simple modification of the fastest known algorithm and runs in Õ(mlog2n) time, an O(log n) factor faster than before. The second algorithm runs in Õ(m log n) time and generates a sparsifier with Õ(n log3n) edges. The third algorithm applies to graphs where m > n log5n and runs in Õ(m log m/nlog5 n n) time. In the range where m > n1+r for some constant r this becomes Õ(m). The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of dense SDD matrices.

AB - We present three spectral sparsification algorithms that, on input a graph G with n vertices and m edges, return a graph H with n vertices and O(n log n/e2) edges that provides a strong approximation of G. Namely, for all vectors x and any ε > 0, we have (1 - ε)xT L Gx ≤ x LHx ≤ (1 + ε)xT L Gx, where LG and LH are the Laplacians of the two graphs. The first algorithm is a simple modification of the fastest known algorithm and runs in Õ(mlog2n) time, an O(log n) factor faster than before. The second algorithm runs in Õ(m log n) time and generates a sparsifier with Õ(n log3n) edges. The third algorithm applies to graphs where m > n log5n and runs in Õ(m log m/nlog5 n n) time. In the range where m > n1+r for some constant r this becomes Õ(m). The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of dense SDD matrices.

KW - Linear system solving

KW - Spectral sparsification

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

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

U2 - 10.4230/LIPIcs.STACS.2012.266

DO - 10.4230/LIPIcs.STACS.2012.266

M3 - Conference contribution

AN - SCOPUS:84880318400

SN - 9783939897354

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 266

EP - 277

BT - 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012

T2 - 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012

Y2 - 29 February 2012 through 3 March 2012

ER -