Premium
Improving the arithmetic intensity of multigrid with the help of polynomial smoothers
Author(s) -
Ghysels P.,
Kłosiewicz P.,
Vanroose W.
Publication year - 2012
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.1808
Subject(s) - mathematics , stencil , memory footprint , multigrid method , polynomial , floating point , smoothing , computation , algorithm , arithmetic , computer science , computational science , mathematical analysis , partial differential equation , statistics , operating system
SUMMARY 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 © 2012 John Wiley & Sons, Ltd.