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
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.