A new perspective on strength measures in algebraic multigrid

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. Copyright (C) 2009 John Wiley & Sons, Ltd.