Smoothed aggregation solvers for anisotropic diffusion

A smoothed aggregation-based algebraic multigrid solver for anisotropic diffusion problems is presented. Algebraic multigrid is a popular and effective method for solving sparse linear systems that arise from discretizing partial differential equations. However, although algebraic multigrid was designed for elliptic problems, the case of non-grid-aligned anisotropic diffusion is not adequately addressed by existing methods. To achieve scalable performance, it is shown that neither new coarsening nor new relaxation strategies are necessary. Instead, a novel smoothed aggregation approach is developed that combines long-distance interpolation, coarse-grid injection, and an energy-minimization strategy that finds the interpolation weights. Previously developed theory by Falgout and Vassilevski is used to discern that existing coarsening strategies are sufficient, but that existing interpolation methods are not. In particular, an interpolation quality measure tracks closeness to the ideal interpolant and guides the interpolation sparsity pattern choice. Although the interpolation quality measure is computable for only small model problems, an inexact, but computable, measure is proposed for larger problems. This paper concludes with encouraging numerical results that also potentially show broad applicability (e.g., for linear elasticity). Copyright (C) 2012 John Wiley & Sons, Ltd.