Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball
Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball
复制标题
在近线性时间内求解 1-拉普拉斯算子：拓扑球的折叠和展开
DOI：
10.1137/1.9781611973402.15
复制
发表时间：
2014
期刊：
影响因子：
8.3
通讯作者：
N. Walkington
中科院分区：
文献类型：
--
作者：
Michael B. Cohen;Brittany Terese Fasy;G. Miller;A. Nayyeri;Richard Peng;N. Walkington
我们提出了一个有效的算法来解决线性系统所产生的1-拉普拉斯对应的可折叠单纯复形与已知的折叠序列。结合Chillingworth的一个结果，我们的算法适用于嵌入R3中的凸单纯复形。我们的算法的运行时间是近线性的复杂的大小，其数值特性是对数。
我们的算法是基于投影算子和组合步骤之间的转移。前者依赖于使用快速求解器将流分解为循环和势流，后者将高斯消除与单纯复形的拓扑性质相关联。
We present an efficient algorithm for solving a linear system arising from the 1-Laplacian corresponding to a collapsible simplicial complex with a known collapsing sequence. When combined with a result of Chillingworth, our algorithm is applicable to convex simplicial complexes embedded in R3. The running time of our algorithm is nearly-linear in the size of the complex and is logarithmic on its numerical properties.
Our algorithm is based on projection operators and combinatorial steps for transferring between them. The former relies on decomposing flows into circulations and potential flows using fast solvers for graph Laplacians, and the latter relates Gaussian elimination to topological properties of simplicial complexes.