next up previous
Next: A Micro-kernel for Grid Up: Generic Components for Grid Previous: Introduction


Analysis of grids and algorithms

The common mathematical basis underlying all incarnations of grids can be captured by the notions of combinatorial topology (see e. g. (13)) and polytope theory (20). Without going into the details (which can be found in (4)), we introduce some basic terminology, necessary to understand the following.

Figure: A simple grid $ {\cal G}$ ...
\includegraphics[width=5cm]{bilder/cellcx-2triang}

Figure: ...and its incidence lattice
\includegraphics[width=5cm]{bilder/cellcx-2triang-lattice}

A simple 2-dimensional grid is shown in figure 2(a). It consists of just two cells, five edges and four vertices. The core of any representation in a computer is formed by the grid's combinatorial structure (fig. 2(b)), namely the incidence relationships between its elements (that is, vertices, edges and cells). Two elements are incident of one is contained in the boundary of the other; for example, $ v_4$ is incident to $ e_4$, $ e_5$ and $ c_2$, and vice versa. This relationship is reflected in the lattice 2(b), which is, roughly spoken, the graph of incidences.

These notions generalize easily to higher dimensions, the three-dimensional case being by far the most important one. A grid $ {\cal G}$ of dimension $ d$ consists of elements of dimension 0 (vertices - $ {\cal G}^0$), dimension $ 1$ (edges - $ {\cal G}^1$), up to dimension $ d$ (cells - $ {\cal G}^d$). The boundary of an element must be composed of lower-dimensional elements (e. g. the boundary of $ c_1$ consists of $ v_1,v_2,v_3, e_1,e_2,e_3$); and the intersection of any two elements must be another element or empty. The mathematical term for such a structure is CW-complex.

We call elements of dimension $ d-1$ (co-dimension $ 1$) facets, which for $ d=2$ coincides with edges. The reason for this additional name is, that many algorithms can be formulated in a dimension-independent way by using the codimension-related terms cell and facet.

Grids may differ in the pattern of incidence relationship they allow, for instance, a Cartesian grid has a very rigid checkerboard pattern, whereas unstructured grids allow for general cell types and connectivity (fig. 1).


In addition to these combinatorial properties, a grid bears also geometric information: it is embedded into some geometric space. The most common case is a planar straight line embedding; other possibilities are curved elements or embeddings into higher dimensional space or into a manifold, for example the surface of a sphere. Straight line embeddings (cf. figs 1 and 2(a)) can be represented by simply assigning space coordinates to vertices. General embeddings, however, are representable only in an approximate way, which is in sharp contrast to the combinatorial information.

Thus, it proves advantageous to preserve the separation of combinatorial and geometric aspects also in the software design, leading to a variety of combinations of the corresponding representations.


Finally, a mathematical concept often overlooked is that of a function on the (discrete) set of grid elements, yielding values of some arbitrary type $ T$. Such grid functions are extremely important to almost every algorithm on grids. Yet they are often provided only half-heartedly or in an ad-hoc fashion, that depends on the needs of the concrete algorithms to be supported.


After clarification of the mathematical concepts, a second step consists in the analysis of representative grid algorithms. It turns out that many of them pose rather modest requirements on functionality of grid data structures, which can be captured by a small set of concepts.

A typical algorithm is the determination of the total flux into a cell across its boundary. Performed for all cells of a grid $ {\cal G}$, this is the core of the finite volume (FV) method:
\begin{algorithmic}[1]
\sf\IN a cell-based state $U: {\cal G}^d \mapsto \mathbb{...
...flux}(c) $\ += $\mbox{numerical\_flux}(c,f,U)$ \ENDFOR
\ENDFOR
\end{algorithmic}
What kind of functionality does this algorithm require? We must iterate over all cells of a grid, as well as over all facets of a cell, and associate states $ U$ and flux to cells. That is, $ U$ and flux are grid functions on cells. Moreover, in numerical_flux(), geometric data like cell centers, facet volumes and normals are required (not shown). We note that the algorithm above is formulated in a dimension independent way (except, of course, the interior of the routine numerical_flux()).

In general, the requirements of most algorithms on grid data structures can be grouped as follows:

In addition, a few algorithms have special requirements on grids, for example does the calculation of cell neighbors require that facets be uniquely determined by their vertex sets. Also, in cases like finite element methods, more information about the combinatorial structure of grid cells is required, see (4) for details.


next up previous
Next: A Micro-kernel for Grid Up: Generic Components for Grid Previous: Introduction
Guntram Berti 2000-09-29