Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices
Authors:
Open Access
- 8 December 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 12 (2) , 1-16
Abstract
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-ϵ ) x T L G x ≤ x T L G˜ x ≤ (1+ϵ) x T L G x , where L G and G˜ are the Laplacians of G and G˜ respectively. The first contribution of this article applies to all existing sparsification algorithms that rely on solving solving linear systems on graph Laplacians. These algorithms are the fastest known to date. Specifically, we show that less precision is required in the solution of the linear systems, leading to speedups by an O (log n ) factor. We also present faster sparsification algorithms for slightly dense graphs: — An O ( m log n ) time algorithm that generates a sparsifier with O ( n log 3 n /ϵ 2 ) edges. — An O ( m log log n ) time algorithm for graphs with more than n log 5 n log log n edges. — An O ( m ) algorithm for graphs with more than n log 10 n edges. — An O ( m ) algorithm for unweighted graphs with more than n log 8 n edges. These bounds hold up to factors that are in O ( poly (log log n )) and are conjectured to be removable.Keywords
All Related Versions
Funding Information
- National Science Foundation (NSF) CAREER (CCF-1149048)
- NSF graduate fellowship
- NSF (CCF-1018463)
- Microsoft Research Fellowship
This publication has 17 references indexed in Scilit:
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear SystemsSIAM Journal on Matrix Analysis and Applications, 2014
- Approaching Optimality for Solving SDD Linear SystemsSIAM Journal on Computing, 2014
- Using petal-decompositions to build a low stretch spanning tree2012
- Spectral Sparsification in the Semi-streaming SettingTheory of Computing Systems, 2012
- Spectral Sparsification of GraphsSIAM Journal on Computing, 2011
- Graph Sparsification by Effective ResistancesSIAM Journal on Computing, 2011
- Random walks and local cuts in graphsLinear Algebra and its Applications, 2007
- Database-friendly random projections: Johnson-Lindenstrauss with binary coinsJournal of Computer and System Sciences, 2003
- Extensions of Lipschitz mappings into a Hilbert space1984
- Applications of Path Compression on Balanced TreesJournal of the ACM, 1979