Improving the arithmetic intensity of multigrid with the help of polynomial smoothers

The basic building blocks of a classic multigrid algorithm, which are essentially stencil computations, all have a low ratio of executed floating point operations per byte fetched from memory. This important ratio can be identified as the arithmetic intensity. Applications with a low arithmetic intensity are typically bounded by memory traffic and achieve only a small percentage of the theoretical peak performance of the underlying hardware. We propose a polynomial Chebyshev smoother, which we implement using cache-aware tiling, to increase the arithmetic intensity of a multigrid V-cycle. This tiling approach involves a trade-off between redundant computations and cache misses. Unlike common conception, we observe optimal performance for higher degrees of the smoother. The higher-degree polynomial Chebyshev smoother can be used to smooth more than just the upper half of the error frequencies, leading to better V-cycle convergence rates. Smoothing more than the upper half of the error spectrum allows a more aggressive coarsening approach where some levels in the multigrid hierarchy are skipped. Copyright (C) 2012 John Wiley & Sons, Ltd.