2026-08-17T09:37:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3434 2024-03-06T10:34:11Z ddc:004 open_access

Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices Koutis, Ioannis Levin, Alex Peng, Richard Spectral sparsification linear system solving We present three spectral sparsification algorithms that, on input a graph G with n vertices and m edges, return a graph H with n vertices and O(n log n/epsilon^2) edges that provides a strong approximation of G. Namely, for all vectors x and any epsilon>0, we have (1-epsilon) x^T L_G x <= x^T L_H x <= (1+epsilon) x^T L_G x, where L_G and L_H are the Laplacians of the two graphs. The first algorithm is a simple modification of the fastest known algorithm and runs in tilde{O}(m log^2 n) time, an O(log n) factor faster than before. The second algorithm runs in tilde{O}(m log n) time and generates a sparsifier with tilde{O}(n log^3 n) edges. The third algorithm applies to graphs where m>n log^5 n and runs in tilde{O}(m log_{m/ n log^5 n} n time. In the range where m>n^{1+r} for some constant r this becomes softO(m). The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of dense SDD matrices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ioannis Koutis and Alex Levin and Richard Peng 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.266 urn:nbn:de:0030-drops-34348 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.266 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode