Adaptive AMG with coarsening based on compatible weighted matching
Adaptive AMG with coarsening based on compatible weighted matching
复制标题
DOI：
10.1007/s00791-014-0224-9
复制
发表时间：
2013-04
影响因子：
--
通讯作者：
P. D'Ambra;P. Vassilevski
中科院分区：
文献类型：
--
作者：
P. D'Ambra;P. Vassilevski
我们提出了一种新的复合自适应代数多重网格(CompositeAMG)方法来求解线性方程组，而不需要对AMG预条件问题的近零分量的特征进行先验知识或假设，称为代数光滑性。我们的AMG版本是一个通过引导策略构建的复合求解器，旨在获得所需的收敛速度。用于构建每个新的求解器组件的粗化过程依赖于基于图中加权匹配的成对聚集方案，该方案被成功地用于稀疏直接方法中的重新排序算法以增强对角优势和兼容松弛。所提出的相容匹配过程取代了在粗空间选择和内插方案中对连接强度的常用表征。我们的目标是设计一种方法来解决超越标准椭圆型偏微分方程(PDE)的一大类问题的可伸缩AMG。在本文中，我们介绍了这种方法，并证明了它在结构网格和非结构网格上应用于高各向异性椭圆型偏微分方程组的有限元离散所产生的对称正定线性方程组的潜力。我们还报告了2D和3D弹性问题的一些初步测试，以及佛罗里达大学稀疏矩阵收藏的问题。
We introduce a new composite adaptive Algebraic Multigrid (compositeAMG) method to solve systems of linear equations without a-priori knowledge or assumption on characteristics of near-null components of the AMG preconditioned problem referred to asalgebraic smoothness. Our version ofAMG is a composite solver built through a bootstrap strategy aimed to obtain a desired convergence rate. The coarsening process employed to build each new solver component relies on a pairwise aggregation scheme based on weighted matching in a graph, successfully exploited for reordering algorithms in sparse direct methods to enhance diagonal dominance, and compatible relaxation. The proposed compatible matching process replaces the commonly used characterization of strength of connection in both the coarse space selection and in the interpolation scheme. The goal is to design a method leading to scalable AMG for a wide class of problems that go beyond the standard elliptic Partial Differential Equations (PDEs). In the present work, we introduce the method and demonstrate its potential when applied to symmetric positive definite linear systems arising from finite element discretization of highly anisotropic elliptic PDEs on structured and unstructured meshes. We also report on some preliminary tests for 2D and 3D elasticity problems as well as on problems from the University of Florida Sparse Matrix Collection.