Convergence in Norm of Nonsymmetric Algebraic Multigrid
Convergence in Norm of Nonsymmetric Algebraic Multigrid
复制标题
非对称代数多重网格范数的收敛性
DOI：
--
复制
发表时间：
2018
影响因子：
3.1
通讯作者：
B. Southworth
中科院分区：
文献类型：
--
作者：
T. Manteuffel;B. Southworth
快速线性求解器和预处理器是针对对称正定 (SPD) 矩阵而开发的。已经为许多感兴趣的系统开发了线性或近线性复杂性（“快速”）算法，并且在许多情况下，已经在收敛性上建立了理论结果。在理论和实践中，非对称设置对 SPD 矩阵提出了许多独特的挑战。开发快速且鲁棒的非对称线性求解器是一个活跃的研究领域，特别是快速非对称求解器的理论结果是有限的。
代数多重网格 (AMG) 是求解大型稀疏线性系统最快的数值方法之一。对于 SPD 矩阵，A 范数中的 AMG 收敛性很好，并且 AMG 已被证明是许多应用的有效求解器。最近，开发了几种对非对称线性系统有效的 AMG 算法。尽管在每种情况下都提供了动机，但非对称线性系统的 AMG 收敛性仍然没有得到很好的理解，并且算法主要基于启发式或不完整的理论。有几部作品深入研究了 NS-AMG 的收敛性，但尚未对收敛条件进行深入研究，特别是对求解器开发的实际影响。在这里，我们提出了第一个这样的工作，讨论了为什么 SPD 理论在非对称设置下失效，并开发了 NS-AMG 收敛的通用框架。经典的多重网格弱逼近和强逼近性质被推广为“分数逼近性质”，并为$sqrt{A^*A}$范数中的两网格和多重网格收敛开发了条件。
Fast linear solvers and preconditioners are well developed for symmetric positive definite (SPD) matrices. Linear or near-linear complexity ("fast") algorithms have been developed for many systems of interest and, in many cases, theoretical results have been established on the convergence. The nonsymmetric setting poses a number of unique challenges over SPD matrices, in theory and in practice. Developing fast and robust nonsymmetric linear solvers is an active area of research and, in particular, theoretical results on fast nonsymmetric solvers are limited.
Algebraic multigrid (AMG) is one of the fastest numerical methods to solve large sparse linear systems. For SPD matrices, convergence of AMG is well motivated in the A-norm, and AMG has proven an effective solver for many applications. Recently, several AMG algorithms have been developed that are effective on nonsymmetric linear systems. Although motivation was provided in each case, the convergence of AMG for nonsymmetric linear systems is still not well understood, and algorithms are based largely on heuristics or incomplete theory. Several works have delved into convergence of NS-AMG, but there has yet to be a thorough study on conditions for convergence and, in particular, the practical implications for solver development. Here, we present the first such work, discussing why SPD theory breaks down in the nonsymmetric setting, and developing a general framework for convergence of NS-AMG. Classical multigrid weak and strong approximation properties are generalized to a "fractional approximation property," and conditions developed for two-grid and multigrid convergence in the $sqrt{A^*A}$-norm.