Generic Software Components for Scientific Computing
In my dissertation, I tackled two problems:
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 Grid Algorithms Library.
If you have problems downloading the dissertation, please send me a mail.
You can also try to download from the publisher .
There you can order a printed version, too (ISBN 3-89825-169-1).