文章基本信息

标题：Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices
本地全文：下载
作者：Ioannis Koutis ; Alex Levin ; Richard Peng 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：14
页码：266-277
DOI：10.4230/LIPIcs.STACS.2012.266
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 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.
关键词：Spectral sparsification; linear system solving