\input zb-basic
\input zb-ioport
\iteman{io-port 06070908}
\itemau{Koutis, Ioannis; Levin, Alex; Peng, Richard}
\itemti{Improved spectral sparsification and numerical algorithms for SDD matrices.}
\itemso{D\"urr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th -- March 3rd, 2012. Wadern: Schloss Dagstuhl -- Leibniz Zentrum f\"ur Informatik (ISBN 978-3-939897-35-4). LIPICS -- Leibniz International Proceedings in Informatics 14, 266-277, electronic only (2012).}
\itemab
Summary: 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/\varepsilon^2)$ edges that provides a strong approximation of $G$. Namely, for all vectors $x$ and any $\varepsilon>0$, we have $$(1-\varepsilon) x^T L_G x \leq x^T L_H x \leq (1+\varepsilon) 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 $\tilde{O}(m)$. The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of dense SDD matrices.
\itemrv{~}
\itemcc{}
\itemut{spectral sparsification; linear system solving}
\itemli{doi:10.4230/LIPIcs.STACS.2012.266}
\end