TY - GEN
T1 - Improved spectral sparsification and numerical algorithms for SDD matrices
AU - Koutis, Ioannis
AU - Levin, Alex
AU - Peng, Richard
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 -