Consequently, a rich variety of grid types is in use, including structured, simplicial, hybrid or multi-block grids, and a multitude of different representations exist for most of them. On the other hand, there is a enormous number of practically relevant grid-based algorithms, like numerical discretizations, visualization of scalar and vector fields, mesh generation, optimization and refinement, just to name a few. Many applications employ a number of algorithms originating from a priori unrelated domains, like numerical analysis and graph theory. These are unlikely to be completely mastered by one single person, or maybe not even by a single research group.
Yet, truly reusable algorithmic grid components are rare. One major reason for this seems to be the tight coupling of algorithm implementations to data structures. Virtually every such component the author is aware of commits to a particular grid representation, thus making reuse in different contexts very hard and unattractive, see also [Weihe 97].
To overcome this limitation, we propose a generic approach [Musser and Stepanov, 1988] to grid components. The first step is a domain analysis, where we investigate mathematical foundations stemming from topology and combinatorics, the key features of grid data structures found in different application domains, and the essential requirements of grid-based algorithms relevant to Scientific Computing. We identify the following key concepts capturing major properties of grid data structures: the combinatorial aspects represented by grid elements (vertices, cells etc.), sequential and incidence iterators, further data associations (grid functions), and geometric embeddings.
Generic implementations for a large class of grid-based algorithms can be based on these concepts. Also, basic blocks for building grid data structures are constructed in a generic way, such as neighbor calculations, additional iteration support, and subranges. In a case study on how to promote algorithm reuse beyond the narrow limits of a specific application domain, views (adapters) are provided allowing to view grids as graphs in various ways.
Many aspects relating to grid components, like persistence, conversion and distribution are found to fit well into the framework, and can be encapsulated in dedicated components. In particular, we have developed a conceptual framework for parallel execution of common algorithmic archetypes on distributed grids, such as numerical PDE solution, which translates smoothly into a generic distribution component. Distributed grids can be generated from sequential ones by simply wrapping them with this component [Berti 99] .
The work is largely independent of a particular programming language. However, from a practical point of view, language assistance for the main paradigms chosen is quite important. Among the broadly used languages suitable for Scientific Computing, C++ certainly offers the best support for different paradigms. Consequently, implementations showing the feasibility and usefulness of the approach have been done in this language.
Earlier stages of this work are described in [Bader,Berti 98] , a full account will be found in the author's PhD thesis . Approaches similar in spirit are the integration of graph iterators into the LEDA toolbox [Weihe and Nissen, 96] and the CGAL Project for Computational Geometry.
References