Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices
Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices
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 G˜ that approximates G in an algebraic sense. Concretely, for all vectors x and any ϵ > 0, the graph G˜ satisfies (1-ϵ ) …