First, how can algorithms operating on grids (or meshes) be implemented in a way that is independent of the concrete representation of a grid, and at the same time, sufficiently efficient?

Second, how can the paradigm of geometric partitioning (domain decomposition) which is used for distributed execution of a certain class of grid algorithms, be formalized and implemented in a reusable way, using the techniques of the first part?

The first problem was solved using a generic programming approach in C++: After an extensive analysis of the mathematical concepts underlying grids, the typical requirements pattern of algorithms and the capabilities of grid data structures, a micro-kernel of central grid functionality could be extracted which serves as a basis for generic implementations of algorithms.

The second problem was tackled by introducing abstractions for distributed grids which support a certain class of data-parallel algorithms typical for numerical PDE solution. The data access pattern of such algorithms (stencil) can be described in a very compact way, thus making an automatic creation of the right overlap between grid parts possible. All software components necessary to support distributed grids are implemented in a generic way. This means, that the whole stuff may be reused after writing an adapter to the micro-kernel. Thus, parallelizing a given application is simplified considerably.

The motivation behind my investigation was the complexity of software for sequential (and even more so, parallel) numerical solution of partial differential equations (PDEs). Nevertheless, the results apply to other domains where grids (under the disguise subdivision, triangulation, B-Rep, boundary complex and so on) play a fundamental role, such as computer graphics, solid modeling, computational geometry or computational topology.

For a somewhat more detailed overview, read the introduction .

The software developed forms the core of the GrAL

Download the whole Dissertation (ca. 250 pages):

ps.gz | (2 MB) | |||

(4 MB) | pdf.gz | (3 MB) | This uses the hyperlink-features of PDF. |

You can also try to download from the publisher . There you can order a printed version, too (ISBN 3-89825-169-1).

Guntram Berti Last modified: Thu Jun 14 09:57:31 MET DST 2001