Guntram Berti.
**
A calculus for stencils on arbitrary grids
with applications to parallel PDE solution
**

In Thomas Sonar and Ingo Thomas, editors,
* Proceedings of
GAMM Workshop
``Discrete Modelling and discrete Algorithms in Continuum Mechanics''
*
(Braunschweig, Germany, November 24-25, 2000),
pages 37-46. Logos Verlag Berlin, 2001.

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.