A new perspective on strength measures in algebraic multigrid

Luke N. Olson, Jacob Schroder, Raymond S. Tuminaro

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)713-733
Number of pages21
JournalNumerical Linear Algebra with Applications
Issue number4
StatePublished - Aug 2010


  • Algebraic coarsening
  • Algebraic multigrid (AMG)
  • Smoothed aggregation (SA)

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics


Dive into the research topics of 'A new perspective on strength measures in algebraic multigrid'. Together they form a unique fingerprint.

Cite this