Solving SDD Linear Systems in Nearly m log1/2 n Time
被引:103
作者:
Cohen, Michael B.
论文数: 0引用数: 0
h-index: 0
机构:
MIT, Cambridge, MA 02139 USAMIT, Cambridge, MA 02139 USA
Cohen, Michael B.
[1
]
论文数: 引用数:
h-index:
机构:
Kyng, Rasmus
[2
]
Miller, Gary L.
论文数: 0引用数: 0
h-index: 0
机构:
Carnegie Mellon Univ, Pittsburgh, PA 15213 USAMIT, Cambridge, MA 02139 USA
Miller, Gary L.
[3
]
Pachocki, Jakub W.
论文数: 0引用数: 0
h-index: 0
机构:
Carnegie Mellon Univ, Pittsburgh, PA 15213 USAMIT, Cambridge, MA 02139 USA
Pachocki, Jakub W.
[3
]
Peng, Richard
论文数: 0引用数: 0
h-index: 0
机构:
MIT, Cambridge, MA 02139 USAMIT, Cambridge, MA 02139 USA
Peng, Richard
[1
]
Rao, Anup B.
论文数: 0引用数: 0
h-index: 0
机构:MIT, Cambridge, MA 02139 USA
Rao, Anup B.
Xu, Shen Chen
论文数: 0引用数: 0
h-index: 0
机构:
Yale Univ, New Haven, CT 06520 USA
Carnegie Mellon Univ, Pittsburgh, PA 15213 USAMIT, Cambridge, MA 02139 USA
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.