Faster spectral sparsification and numerical algorithms for SDD matrices

DOI10.1145/2743021MaRDI QIDQ89555zbMATH OpenOpenAlexWikidataFDO

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)

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)

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.

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

Cited in

(14)

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

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)