Solving SDD Linear Systems in Nearly m log1/2 n Time

被引:103
作者
Cohen, Michael B. [1 ]
Kyng, Rasmus [2 ]
Miller, Gary L. [3 ]
Pachocki, Jakub W. [3 ]
Peng, Richard [1 ]
Rao, Anup B.
Xu, Shen Chen [2 ,3 ]
机构
[1] MIT, Cambridge, MA 02139 USA
[2] Yale Univ, New Haven, CT 06520 USA
[3] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA
来源
STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2014年
关键词
combinatorial preconditioning; SDD linear systems; random matrices; tree embeddings; APPROXIMATION;
D O I
10.1145/2591796.2591833
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems with m non -zero entries to a relative error of E in 0(m log1/2 n log log' n log (1/e)) time. Our approach follows the recursive preconditioning framework, which aims to reduce graphs to trees using iterative methods. We improve two key components of this framework: random sampling and tree embeddings. Both of these components are used in a variety of other algorithms, and our approach also extends to the dual problem of computing electrical flows. We show that preconditioners constructed by random sampling can perform well without meeting the standard requirements of iterative methods. In the graph setting, this leads to ultra-sparsifiers that have optimal behavior in expectation. The improved running time makes previous low stretch embedding algorithms the running time bottleneck in this framework. In our analysis, we relax the requirement of these embeddings to snowflake spaces. We then obtain a two -pass approach algorithm for constructing optimal embeddings in snowflake spaces that runs in 0(m log log n) time. This algorithm is also readily parallelizable.
引用
收藏
页码:343 / 352
页数:10
相关论文
empty
未找到相关数据