Robust and adaptive multigrid methods: comparing structured and algebraic approaches

Although there have been significant advances in robust algebraic multigrid (AMG) methods in recent years, numerical studies and emerging hardware architectures continue to favor structured-grid approaches. Specifically, implementations of logically structured robust variational multigrid algorithms, such as the black box multigrid (BoxMG) solver, have been shown to be 10 times faster than AMG for three-dimensional heterogeneous diffusion problems on structured grids. BoxMG offers important features such as operator-induced interpolation for robustness, while taking advantage of direct data access and bounded complexity in the Galerkin coarse-grid operator. Moreover, because BoxMG uses a variational framework, it can be used to explore advances of modern adaptive AMG approaches in a structured setting. In this paper, we show how to extend the adaptive multigrid methodology to the BoxMG setting. This extension not only retains the favorable properties of the adaptive framework but also sheds light on the relationship between BoxMG and AMG. In particular, we show how classical BoxMG can be viewed as a special case of classical AMG and how this viewpoint leads to a richer family of adaptive BoxMG approaches. We present numerical results that explore this family of adaptive methods and compare its robustness and efficiency to the classical BoxMG solver.Copyright (C) 2012 John Wiley & Sons, Ltd.