Premium
A new perspective on strength measures in algebraic multigrid
Author(s) -
Olson Luke N.,
Schroder Jacob,
Tuminaro Raymond S.
Publication year - 2010
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.669
Subject(s) - multigrid method , connection (principal bundle) , mathematics , solver , pointwise , grid , precondition , algebraic number , algebra over a field , mathematical optimization , computer science , partial differential equation , pure mathematics , geometry , mathematical analysis , programming language
Algebraic‐based multilevel solution methods (e.g. classical Ruge–Stüben 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. Copyright © 2009 John Wiley & Sons, Ltd.