Generic Components

One of the purposes of having a micro-kernel is separating the truly representation-dependent issues from those which can be dealt with in a generic manner. Of course, the distinction is not sharp; we will see that even parts of the micro-kernel can be implemented generically based on other parts of the latter. However, there often are better implementations possible, which are specialized to the concrete representation and thus justify their inclusion into the micro-kernel.

This discussion suggests a classification of generic components according to their generality, or proximity to the basic kernel. On the one end ot the scale, we have components that are properly regarded as extending the functionality of grid data structures, for instance iterators, grid functions or grid subranges. On the other end, there are lots of (mostly algorithmic) components fulfilling very domain-specific tasks, such as numerical discretizations, grid smoothing, and so on. Somewhere in between lie data structures like hierarchical or distributed grids.

In the following, we review some generic components having been developed so far, proceeding from more general to more specific. The case of grid functions is discussed in more detail in the next section.

Iterators Sequence as well as incidence iterators can be implemented generically in some cases. For example, sequence iterators for (non-stored) facets can be implemented using cell iterators and facet-on-cell iterators, if there is a total ordering on cells. Incidence iterators on vertices can (in 2D) be based on a so-called switch operation (5). The same technique works for boundary iterators, where one can use arbitrary cell predicates to define inner and outer grid parts.

Grid subranges A grid subrange is defined by a collection of cells, and can be implemented based on cell handles. The elements of lower dimension contained in the closure of the cell set are then given by closure iterators, which use partial grid functions to mark visited elements.

Grid functions Grid functions have two basic parameters of variation: Element type and value type. The value type parameter poses no special problems (cf. STL). Depending on the properties of the element parameter, we can choose a generic implementation using vectors or hash tables, see the next section.

Distributed grids Applications like solution of partial differential equations needing a lot of computational power are candidates for parallel execution. The resulting management of overlapping grid parts is provided by distributed grids. Data structures for representing the overlap ranges, methods for updating distributed grid functions and algorithms for automatic generation of overlapping parts have been based generically on the kernel.

Hierarchical grids Some of the more advanced computational methods (such as the multigrid method below) are based on hierarchies of successively refined grids, with vertical (coarse $\leftrightarrow$ fine) relationships between them.

Multigrid algorithms Multigrid methods (10) are optimal algorithms for solving sparse linear systems `living' on a hierarchy of grids. Grid-related operations, such as the mapping of state vectors and matrices between different grid levels (restriction and prolongation), are implemented generically.

Finite volume discretizations In addition to the basic finite volume algorithm presented before more complex higher-order methods have been implemented, which involve averaging values of cells incident to vertices.

Two prototype generic solvers for PDE problems have been based on the components just mentioned: A finite element solver for the Poisson equation using adaptive grid hierarchies and multigrid algorithms, and a finite volume solver for the incompressible Euler equations. The latter has been parallelized using components for distributed grids. We will come back to these solvers at the end of the paper.