Koutis, Ioannis ;
Levin, Alex ;
Peng, Richard
Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices
Abstract
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/epsilon^2) edges that provides a strong approximation of G. Namely, for all vectors x and any epsilon>0, we have (1epsilon) x^T L_G x <= x^T L_H x <= (1+epsilon) x^T L_G x, where L_G and L_H are the Laplacians of the two graphs. The first algorithm is a simple modification of the fastest known algorithm and runs in tilde{O}(m log^2 n) time, an O(log n) factor faster than before. The second algorithm runs in tilde{O}(m log n) time and generates a sparsifier with tilde{O}(n log^3 n) edges. The third algorithm applies to graphs where m>n log^5 n and runs in tilde{O}(m log_{m/ n log^5 n} n time. In the range where m>n^{1+r} for some constant r this becomes softO(m). The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of dense SDD matrices.
BibTeX  Entry
@InProceedings{koutis_et_al:LIPIcs:2012:3434,
author = {Ioannis Koutis and Alex Levin and Richard Peng},
title = {{Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {266277},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3434},
URN = {urn:nbn:de:0030drops34348},
doi = {10.4230/LIPIcs.STACS.2012.266},
annote = {Keywords: Spectral sparsification, linear system solving}
}
2012
Keywords: 

Spectral sparsification, linear system solving 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

2012 