An Empirical Study of Cycle Toggling Based Laplacian Solvers
An Empirical Study of Cycle Toggling Based Laplacian Solvers
复制标题
基于循环切换的拉普拉斯求解器的实证研究
DOI：
10.1137/1.9781611974690.ch4
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Xu, Shen Chen
中科院分区：
文献类型：
--
作者：
Deweese, Kevin;Gilbert, John R;Miller, Gary;Peng, Richard;Xu, Hao Ran;Xu, Shen Chen
基于[Kelner-Orecchia-Sidford-朱斯托克-13]提出的组合循环调整方法，我们研究了图拉普拉斯的线性求解器的性能。该方法通过沿循环进行一系列流量调整，找到该线性系统的双流解。我们研究了面向数据结构和递归方法来处理这些调整，这种方法面临的主要困难是更新和查询长循环，这促使我们研究了一个重要的特殊情况：所有循环都是由长度为n的路径上的基本循环形成的实例。我们的方法比以前的实现有显著的加速比，并且与标准的数值例程相比具有竞争力。
We study the performance of linear solvers for graph Laplacians based on the combinatorial cycle adjustment methodology proposed by [Kelner-Orecchia-Sidford-Zhu STOC-13]. The approach finds a dual flow solution to this linear system through a sequence of flow adjustments along cycles. We study both data structure oriented and recursive methods for handling these adjustments.The primary difficulty faced by this approach, updating and querying long cycles, motivated us to study an important special case: instances where all cycles are formed by fundamental cycles on a length n path. Our methods demonstrate significant speedups over previous implementations, and are competitive with standard numerical routines.
登录
查看更多内容
回归问题的运行时保证
DOI：
--
发表时间：
2011
期刊：
Information Technology Convergence and Services
影响因子：
--
作者：
Hui Han Chin;A. Madry;G. Miller;Richard Peng
通讯作者：
Richard Peng
DOI：
10.1137/1.9780898718003
发表时间：
2003-05
期刊：
--
影响因子：
--
作者：
Y. Saad
通讯作者：
Y. Saad
图拉普拉斯求解器的实证比较
DOI：
--
发表时间：
2016
期刊：
Workshop on Algorithm Engineering and Experimentation
影响因子：
--
作者：
E. Boman;Kevin Deweese;J. Gilbert
通讯作者：
J. Gilbert
用于连接拉普拉斯的稀疏 Cholesky 和多重网格求解器
DOI：
--
发表时间：
2015
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Rasmus Kyng;Y. Lee;Richard Peng;Sushant Sachdeva;D. Spielman
通讯作者：
D. Spielman
列表排序和并行树收缩
DOI：
--
发表时间：
1993
期刊：
影响因子：
--
作者：
M. Reid;G. Miller;F. Modugno
通讯作者：
F. Modugno