Title
|
|
|
|
Improving the arithmetic intensity of multigrid with the help of polynomial smoothers
|
|
Author
|
|
|
|
|
|
Abstract
|
|
|
|
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. |
|
|
Language
|
|
|
|
English
|
|
Source (journal)
|
|
|
|
Numerical linear algebra with applications. - Chichester
|
|
Publication
|
|
|
|
Chichester
:
Wiley
,
2012
|
|
ISSN
|
|
|
|
1070-5325
|
|
DOI
|
|
|
|
10.1002/NLA.1808
|
|
Volume/pages
|
|
|
|
19
:2
(2012)
, p. 253-267
|
|
ISI
|
|
|
|
000299777500006
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|
Full text (publisher's version - intranet only)
|
|
|
|
|
|