  We study algorithms for spectral graph sparsification. The input is a graph
$G$ with $n$ vertices and $m$ edges, and the output is a sparse graph
$\tilde{G}$ that approximates $G$ in an algebraic sense. Concretely, for all
vectors $x$ and any $\epsilon>0$, $\tilde{G}$ satisfies $$ (1-\epsilon) x^T L_G
x \leq x^T L_{\tilde{G}} x \leq (1+\epsilon) x^T L_G x, $$ where $L_G$ and
$L_{\tilde{G}}$ are the Laplacians of $G$ and $\tilde{G}$ respectively. We show
that the fastest known algorithm for computing a sparsifier with $O(n\log
n/\epsilon^2)$ edges can actually run in $\tilde{O}(m\log^2 n)$ time, an
$O(\log n)$ factor faster than before. We also present faster sparsification
algorithms for slightly dense graphs. Specifically, we give an algorithm that
runs in $\tilde{O}(m\log n)$ time and generates a sparsifier with
$\tilde{O}(n\log^3{n}/\epsilon^2)$ edges. This implies that a sparsifier with
$O(n\log n/\epsilon^2)$ edges can be computed in $\tilde{O}(m\log n)$ time for
graphs with more than $O(n\log^4 n)$ edges. We also give an $\tilde{O}(m)$ time
algorithm for graphs with more than $n\log^5 n (\log \log n)^3$ edges of
polynomially bounded weights, and an $O(m)$ algorithm for unweighted graphs
with more than $n\log^8 n (\log \log n)^3 $ edges and $n\log^{10} n (\log \log
n)^5$ edges in the weighted case. The improved sparsification algorithms are
employed to accelerate linear system solvers and algorithms for computing
fundamental eigenvectors of slightly dense SDD matrices.
