Faster spectral sparsification and numerical algorithms for SDD matrices

DOI10.48550/arXiv.1209.5821zbMath1398.68403arXiv1209.5821OpenAlexW2135927639MaRDI QIDQ89555

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

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

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

Related Items (4)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ simplifyNet ⋮ 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