Typical algorithms in scientific computing, such as finite element methods for the numerical solution of partial differential equations, require a grid to discretize the domain where the solution of the equation is sought. Modern methods frequently need more than one grid, for a number of reasons. Important examples are adaptive grids--grids that are coarsened or refined in some areas because of an erratic behavior of the solution there--and algorithms of multigrid type that use a hierarchy of grids in an attempt to improve the ratio between accuracy and runtime. In either case, one has to provide a suitable concept for the modeling of the grids themselves and for the operations performed on the grids (refinement, coarsening, and so on).

While these points seem very simple from an intuitive point of view, it actually turns out that a precise abstract mathematical formulation that allows efficient algorithms for the practical handling of these questions is surprisingly difficult to obtain. The Distributed and Unified Numerics Environment (DUNE) project (http://dune-project.org) provides such an abstract framework.

The goal of the paper is to provide a mathematically rigorous description of this framework. The concrete C++ implementation of the concepts is described in a companion paper [1].