next up previous
Next: Bibliography Up: Generic Components for Grid Previous: Some Recurring Difficulties


Discussion

In this paper, we have described a micro-kernel as a basis for generic programming in the domain of grids and grid algorithms. The generic approach gains increasing attention in the field of scientific computing. To our knowledge, the work presented here is the first to successfully apply this paradigm to arbitrary grids used in this field. All libraries for numerical PDE solution that are using generic programming techniques and known to the author work on specific grid data structures, either structured grids (e. g. (6)), semi-structured (e. g. (16)) or unstructured (e. g. (9)).

Widening the focus beyond PDE solution two examples that perhaps come closest to our work in scope and problem domain are CGAL (Computational Geometry Algorithms Library, (8,17)) and GGCL (Generic Graph Component Library, (11,19,12)). Also, the LEDA library (14) -- which by itself does not offer generic algorithms -- has been enhanced with graph iterators (GIT - Graph Iterator Extension, (15)) to support generic graph algorithms.

CGAL offers data structures and algorithms used in geometric computing, such as convex hulls and Delaunay triangulations, which correspond to the grid data structures treated here. The equivalent of incidence iterators is given by circulators in 2D. Grid functions are not supported as a separate entity; instead, one can parameterize some data structures by the type of data stored on the elements like vertices or faces. This has the disadvantage of coupling the data structures to the set of algorithms using them. On the whole, implementations of algorithms on grids seem to be slanted towards the particular family of half-edge data structures used in CGAL, thus limiting their reuse in different contexts.

GGCL implements generic graph algorithms and data structures. The equivalent of incidence iterators is modeled by a sort of `virtual container' concept, making it possible for instance to access all edges adjacent to a given node. Instead of grid functions, one can use a decorator pattern to achieve a similar effect, but which lacks the uniformity of our approach.

Graphs can be obtained from grids in several ways, by stripping off some structure and the geometric aspects. As many algorithms on grids, for example grid partitioning, can be formulated on graphs in a more general way, using algorithms from a generic graph library like GGCL would be highly interesting. For each of the several possibilities of viewing a grid as graph, only one single adapter would have to be written. This adaptation is scheduled for the near future.


What we have described here touches only a small part of the work presented in (4). Two complete applications for the numerical solution of partial differential equations have been developed, one using FEM and adaptive multigrid, the other using a FV approach.

Of course, the generic approach does not make the task of developing a single PDE solver much easier -- much preliminary effort has to go into the domain analysis and development of reusable components. But once on can build on this effort, the approach has considerable advantages. For instance, even if the underlying grid type is not intended to be changed, the micro-kernel layer effectively shields algorithmic code from changes to the low-level data representation, thus making later optimizations much easier. A typical example for such optimizations is the decision whether to store or to compute certain geometric quantities, a question which can be answered only on the basis of the concrete algorithms used.

To date, one of the most convincing proofs of the viability of the approach is given by parallel PDE solution. The distributed grid components mentioned above have been employed successfully to parallelize a generic FV solver, as well as a pre-existing Navier-Stokes solver (1). For the latter, in order to generate a distributed version of the code, only a simple adapter mapping the functionality of the original grid data structure to the micro-kernel had to be written, and some localized changes to the numerical code had to be made. So, work that normally requires several months could be achieved within a few days.

The full potential of the generic method becomes visible when producing whole families of PDE solvers. At present, a rather small family is implemented, allowing a FV solver to vary -- besides grid and geometry -- the type of the (hyperbolic) equation to solve, and, by selecting the appropriate grid type, to choose whether code for sequential or distributed computation is generated. As grid data structures represent only a small part of the parameters of variation, there is much opportunity for future extensions. Also, a more systematic approach to implementing grid data structures is promising, using e. g. principles of generative programming (7).


Currently, the code is being prepared for public release (3).


next up previous
Next: Bibliography Up: Generic Components for Grid Previous: Some Recurring Difficulties
Guntram Berti 2000-09-29