Faster spectral sparsification and numerical algorithms for SDD matrices

DOI10.1145/2743021zbMATH Open1398.68403arXiv1209.5821OpenAlexW2135927639WikidataQ130956878 ScholiaQ130956878MaRDI QIDQ89555FDOQ89555

Richard Peng, Ioannis Koutis, Alex Levin, Richard Peng, Alex Levin, Ioannis Koutis

Publication date: 26 September 2012

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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 $ildeG$ that approximates $G$ in an algebraic sense. Concretely, for all vectors $x$ and any $epsilon>0$, $ildeG$ satisfies ${\displaystyle }$ (1-epsilon) x^T L_G x leq x^T L_{ ilde{G}} x leq (1+epsilon) x^T L_G x, ${\displaystyle }$ where $L_G$ and $L_{ildeG}$ are the Laplacians of $G$ and $ildeG$ respectively. We show that the fastest known algorithm for computing a sparsifier with $O(nlogn/epsilo{n}^2)$ edges can actually run in $ildeO(mlo{g}^{2}n)$ time, an $O(logn)$ factor faster than before. We also present faster sparsification algorithms for slightly dense graphs. Specifically, we give an algorithm that runs in $ildeO(mlogn)$ time and generates a sparsifier with $ildeO(nlo{g}^{3}n/epsilo{n}^2)$ edges. This implies that a sparsifier with $O(nlogn/epsilo{n}^2)$ edges can be computed in $ildeO(mlogn)$ time for graphs with more than $O(nlo{g}^{4}n)$ edges. We also give an $ildeO(m)$ time algorithm for graphs with more than $nlo{g}^{5}n(loglogn{)}^3$ edges of polynomially bounded weights, and an $O(m)$ algorithm for unweighted graphs with more than $nlo{g}^{8}n(loglogn{)}^3$ edges and $nlo{g}^{10}n(loglogn{)}^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.

Full work available at URL: https://arxiv.org/abs/1209.5821

zbMATH Keywords

spectral sparsificationsymmetric diagonally dominant (SDD) matrices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational methods for sparse matrices (65F50) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cited In (6)

• Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices
• Density Independent Algorithms for Sparsifying k-Step Random Walks
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• simplifyNet
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

This page was built for publication: Faster spectral sparsification and numerical algorithms for SDD matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q89555)