Faster spectral sparsification and numerical algorithms for SDD matrices

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

Authors: Ioannis Koutis, Alex Levin, Richard Peng, Ioannis Koutis, Alex Levin, Richard Peng 

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

Recommendations

• Improved spectral sparsification and numerical algorithms for SDD matrices
• Spectral sparsification of graphs
• Approaching optimality for solving SDD linear systems
• An SDP-based algorithm for linear-sized spectral sparsification
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

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 (14)

• Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices
• Constructing linear-sized spectral sparsification in almost-linear time
• Determinant-preserving sparsification of SDDM matrices
• Spectral sparsification of graphs
• Improved spectral sparsification and numerical algorithms for SDD matrices
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Algorithms, graph theory, and linear equations in Laplacian matrices
• simplifyNet
• An SDP-based algorithm for linear-sized spectral sparsification
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Density independent algorithms for sparsifying \(k\)-step random walks
• A matrix hyperbolic cosine algorithm and applications
• On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
• Sparse sums of positive semidefinite 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)