Deriving Skeletons For Multigrid Algorithms

Algorithmic skeletons are polymorphic higher-order functions that implement parallel processing patterns. In this paper, we address the issue of using skeletons in the parallel implementation of multigrid algorithms. We study the data access and communication patterns employed in these methods and derive from them a set of skeletons, which can be used as the building blocks for most multigrid algorithms. We concentrate on a basic multigrid component, the relaxation, and show how different relaxation methods can be implemented by means of our skeletons