Incomplete nested dissection
Incomplete nested dissection
复制标题
不完整的嵌套解剖
DOI：
10.1145/3188745.3188960
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Zhang, Peng
中科院分区：
文献类型：
--
作者：
Kyng, Rasmus;Peng, Richard;Schwieterman, Robert;Zhang, Peng
我们提出了一个渐近快速算法求解线性系统的结构良好的三维桁架刚度矩阵。这些线性系统产生于线性弹性问题，并且可以被看作是图拉普拉斯算子到更高维度的扩展。利用图拉普拉斯算子求解工具的推广[Daitch-Spielman CSC'07，Shklarski-Toledo SIMAX'08]，研究了这类系统的二维变形的快速求解器（四面体网格）与有界的纵横比，其个别四面体也在某种意义上良好的条件，我们的算法在相关的刚度矩阵中求解线性系统，其精度在时间上为O（k1/3 n5/3log（1 /k））。这渐近地改善了运行时间O（n2）的嵌套剖分为allk n。我们还给出了一个结果，改善了嵌套剖分，即使我们允许任何纵横比的每一个thek凸结构（但我们仍然需要良好条件的个人四面体）。在此基础上，我们对嵌套剖分叉KNN 1/44进行了改进。算法的核心思想是将嵌套剖分与支撑理论联合收割机相结合。这两种求解线性系统的方法都得到了很好的研究，但通常是分开的。我们的算法分解成独立的和平衡的区域小边界的三维桁架。然后，我们分别绑定每个这样的区域的频谱，并利用这样的边界，以获得改进的算法，通过预处理与基于分离器的高斯消除的部分状态。
We present an asymptotically faster algorithm for solving linear systems in well-structured 3-dimensional truss stiffness matrices. These linear systems arise from linear elasticity problems, and can be viewed as extensions of graph Laplacians into higher dimensions. Faster solvers for the 2-D variants of such systems have been studied using generalizations of tools for solving graph Laplacians [Daitch-Spielman CSC’07, Shklarski-Toledo SIMAX’08].Given a 3-dimensional truss overnvertices which is formed from a union ofkconvex structures (tetrahedral meshes) with bounded aspect ratios, whose individual tetrahedrons are also in some sense well-conditioned, our algorithm solves a linear system in the associated stiffness matrix up to accuracy є in timeO(k1/3n5/3log(1 / є)). This asymptotically improves the running timeO(n2) by Nested Dissection for allk≪n.We also give a result that improves on Nested Dissection even when we allow any aspect ratio for each of thekconvex structures (but we still require well-conditioned individual tetrahedrons). In this regime, we improve on Nested Dissection fork≪n1/44.The key idea of our algorithm is to combine nested dissection and support theory. Both of these techniques for solving linear systems are well studied, but usually separately. Our algorithm decomposes a 3-dimensional truss into separate and balanced regions with small boundaries. We then bound the spectrum of each such region separately, and utilize such bounds to obtain improved algorithms by preconditioning with partial states of separator-based Gaussian elimination.
登录
查看更多内容
有限元矩阵中的刚度：结构和子结构刚度的充分条件
DOI：
10.1137/060650295
发表时间：
2008
期刊：
SIAM J. Matrix Anal. Appl.
影响因子：
--
作者：
Gil Shklarski;Sivan Toledo
通讯作者：
Sivan Toledo
在近线性时间内求解 1-拉普拉斯算子：拓扑球的折叠和展开
影响因子：
8.3
作者：
Michael B. Cohen;Brittany Terese Fasy;G. Miller;A. Nayyeri;Richard Peng;N. Walkington
通讯作者：
N. Walkington
DOI：
10.1137/1.9780898718003
发表时间：
2003-05
期刊：
--
影响因子：
--
作者：
Y. Saad
通讯作者：
Y. Saad
结构化线性系统的硬度结果
DOI：
10.1109/focs.2017.69
发表时间：
2017
期刊：
58th IEEE Annual Symposium on Foundations of Computer Science,FOCS 2017
影响因子：
--
作者：
Kyng, Rasmus;Zhang, Peng
通讯作者：
Zhang, Peng
O(n loglogn) 时间内平面图中的最小割和最短循环
DOI：
10.1007/978-3-642-23719-5_14
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
Jakub Lacki;P. Sankowski
通讯作者：
P. Sankowski