A new perspective on strength measures in algebraic multigrid

作者：Olson Luke N; Schroder Jacob^*; Tuminaro Raymond S

来源：Numerical Linear Algebra with Applications, 2010, 17(4): 713-733.

DOI：10.1002/nla.669

• algebraic multigrid (AMG)
• smoothed aggregation (SA)
• algebraic coarsening

Algebraic-based multilevel solution methods (e.g. classical Ruge-Stuben and smoothed aggregation style algebraic multigrid) attempt to solve or precondition sparse linear systems without knowledge of an underlying geometric grid. The automatic construction of a multigrid hierarchy relies on strength-of connection information to coarsen the matrix graph and to determine sparsity patterns for the inter-grid transfer operators. Strength-of-connection as a general concept is not well understood and the first task of this paper is therefore on understanding existing strength-of-connection measures and their limitations. In particular, we present a framework to interpret and clarify existing measures through differential equations. This framework leads to a new procedure for making pointwise strength-of-connection decisions that combines knowledge of local algebraically smooth error and of the local behavior of interpolation. The new procedure effectively addresses a variety of challenges associated with strength-of-connection and when incorporated within an algebraic multigrid procedure gives rise to a robust and efficient solver.

• 出版日期2010-8