A calculus for stencils on arbitrary grids
with applications to parallel PDE solution


Guntram Berti
Institut für Mathematik
BTU Cottbus, Germany

Typical algorithms used for numerical PDE solution (such as finite volume discretizations) work locally on structured or unstructured grids. The exact pattern of data access of an algorithm, its stencil, concentrates the information on the algorithm's structural properties.

A stencil can be used to determine the data accessed by the algorithm if executed on a subset of a grid. In our terminology, the data accessed by an algorithm is called hull, and the initial grid subset is called germ. Thus, a hull is a function of a stencil and a germ.

We present a simple, compact algebraic notation for stencils by means of so-called incidence sequences. This algebraic description makes it easy to derive some fundamental results on stencils. For example, we can compare for inclusion the hulls generated by different stencils when applied to a common germ set of cells.

Hulls of stencils are important for determining the correct amount of overlap when solving PDEs in parallel. We present algorithms for efficient generation of stencil hulls, given an arbitrary stencil and a germ of start cells. Starting from a general framework for parallel PDE solution, we implemented these algorithms to provide a universally reusable set of distributed grid components, which are independent of grid data structures and the concrete numerical algorithms used.



Guntram Berti 2000-09-29