Premium
Adaptive reduction‐based AMG
Author(s) -
MacLachlan Scott,
Manteuffel Tom,
McCormick Steve
Publication year - 2006
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.486
Subject(s) - multigrid method , discretization , reduction (mathematics) , matrix (chemical analysis) , mathematics , mathematical optimization , partial differential equation , linear system , convergence (economics) , computer science , mathematical analysis , materials science , geometry , economics , composite material , economic growth
With the ubiquity of large‐scale computing resources has come significant attention to practical details of fast algorithms for the numerical solution of partial differential equations. Included in this group are the class of multigrid and algebraic multigrid algorithms that are effective solvers for many of the large matrix problems arising from the discretization of elliptic operators. Algebraic multigrid (AMG) is especially effective for many problems with discontinuous coefficients, discretized on unstructured grids, or over complex geometries. While much effort has been invested in improving the practical performance of AMG, little theoretical understanding of this performance has emerged. This paper presents a two‐level convergence theory for a reduction‐based variant of AMG, called AMGr, which is particularly appropriate for linear systems that have M ‐matrix‐like properties. For situations where less is known about the problem matrix, an adaptive version of AMGr that automatically determines the form of the reduction needed by the AMGr process is proposed. The adaptive cycle is shown, in both theory and practice, to yield an effective AMGr algorithm. Copyright © 2006 John Wiley & Sons, Ltd.