[Dune] GridPaper...
Oliver Sander
sander at mi.fu-berlin.de
Tue Jun 26 17:49:27 CEST 2007
Hi All!
Here are answers (opinions), wherever I have them:
>
>Some remarks:
>1) should we include the father relation on codim>0 entities.
> This relation is not modeled in DUNE
> (actually subentities are not even part of the interface at the
> moment).
>
>
IMHO subentities are part of the interface. There are methods
to get Leaf- and LevelIterators for entities of all codims; also
the codim-0 entities have a method entity<cd>() which gives
you access to the subentities. Yes, we do not currently require
implementations to provide that functionality, but it is
contained in the interface.
>2) There is some confusion concerning the level II at interior
> level boundaries. Should the II stop in this case and what is
> boundary(), neighbour()... (boundary=neighbor=false?)
> The DUNE documentation seems to say that the II stops in this
> case but the values of boundary() and neighbor() are not mentioned.
> The paper says that no intersection is generated...
>
>
I always thought that LevelIntersectionIterators are supposed
to stop there and return boundary()==neighbor()==false.
UGGrid and OneDGrid are programmed that way, which of
course doesn't mean it's a fortiori correct.
>3) The leaf definition is simpler than before prehaps we have missed
> some problem here? Instead of some sarcastic remark a real
> explanation would be welcomed - if both Robert and myself do not
> see the importants of the original definition than a external
> reader would probably have similar problems...
>
>
I have to admit I don't understand what you mean by this.
Before what? I didn't really change anything there.
I apologize if my comments are too sarcastic for your taste.
greetings,
Oliver
>Have fun
>Robert and Andreas
>
>
>
>
>------------------------------------------------------------------------
>
>\documentclass[12pt,a4paper]{article}
>\usepackage[ansinew]{inputenc}
>\usepackage{amsmath}
>\usepackage{amsfonts}
>\usepackage{amssymb}
>\usepackage{theorem}
>\usepackage{leftidx}
>\usepackage{psfrag}
>\usepackage{graphicx}
>\usepackage{url}
>\usepackage{natbib}
>\bibpunct{[}{]}{,}{n}{}{,}
>
>%The theorems
>\theorembodyfont{\upshape}
>\theoremheaderfont{\bfseries}
>\newtheorem{concept}{Concept}
>\newtheorem{defi}{Definition}
>\newtheorem{note}{Note}
>\newtheorem{rem}{Remark}
>\newtheorem{exmpl}{Example}
>\newtheorem{lst}{Listing}
>
>\def\robert#1{{\bf Robert: #1}}
>\def\andreas#1{{\bf Andreas: #1}}
>\def\mario#1{{\bf Mario #1}}
>\def\peter#1{{\bf Peter #1}}
>\newcommand{\oliver}[1]{{\bf Oliver: #1}}
>\def\old#1{{}}
>
>\title{A Generic Grid Interface for Parallel and
> Adaptive Scientific Computing.\\
> Part I: Abstract Framework}
>
>
>\author{Peter Bastian$^\ast$ \and
>Markus Blatt$^\ast$ \and
>Andreas Dedner$^\dagger$ \and
>Christian Engwer$^\ast$ \and
>Robert Kl\"ofkorn$^\dagger$ \and
>Mario Ohlberger$^\dagger$ \and
>Oliver Sander$^\ddagger$}
>
>\date{
>{\normalsize $^\ast$Interdisziplin\"ares Zentrum f\"ur Wissenschaftliches Rechnen,\\
>Universit\"at Heidelberg,
>Im Neuenheimer Feld 368, D-69120 Heidelberg}\\
>%
>\smallskip
>{\normalsize \textit{now at} Institut f\"ur Parallele und Verteilte Systeme,\\
>Universit\"at Stuttgart,
>Universit\"atsstra\ss e 38, D-70569 Stuttgart}\\
>%
>\bigskip
>{\normalsize $^\dagger$Abteilung f\"ur Angewandte Mathematik, Universit\"at Freiburg,\\
>Hermann-Herder-Str.~10, D-79104 Freiburg}\\
>%
>\bigskip
>{\normalsize $^\ddagger$Institut f\"ur Mathematik II,\\ Freie Universit\"at Berlin,
>Arnimallee 6, D-14195 Berlin,\\DFG Research Center {\sc Matheon}}\\
>%
>\bigskip
>\today
>}
>
>\begin{document}
>
>\maketitle
>\section{Introduction}
>
>% Continuum mechanics, PDEs, Grid based methods
>Partial Differential Equations (PDEs) are abundant in science and
>engineering. There is a large body of methods to numerically solve PDEs,
>such as the finite element, finite volume, and finite
>difference method, as well as grid-less methods. Moreover, there are many
>implementations of these methods in computer codes, see e.~g.~the list
>provided by \cite{feresources}. Traditional finite element codes are
>built upon a fixed data structure for the finite element
>grid. Changing this grid data structure substantially is usually hard and
>very time-consuming.
>
>To overcome the limitations of existing grid-based PDE solvers we
>present the ``Distributed and Unified Numerics Environment'' DUNE,
>(see \cite{duneweb} for the current version of the software). DUNE has a
>component-based software architecture where each component possesses
>an abstract interface and exists in several implementations with
>different features. This concept is realized very efficiently using generic programming
>techniques in C++ which essentially removes the interface overhead
>at compile-time. Moreover, existing software can be used to implement
>the components.
>
>In this article we present a mathematical description of general grids
>as they are used in grid-based PDE solvers. Based on this mathematical
>description a companion paper \cite{gridpaper_part2} describes the
>interface of DUNE's grid component in the form of C++ classes and
>illustrates its functionality and efficiency with some examples.
>When designing the classes for the grid interface we
>felt that a mathematically rigorous description of the entities
>comprising a grid and their complicated relations is required.
>Here, we attempt to formally describe grids with the following
>features:
>\begin{itemize}
>%\item Elements of arbitrary shape and dimension \oliver{The shape is not really arbitrary}
>\item Elements of various shapes and dimension
>\item Embedding in higher dimensional spaces (grids on manifolds)
>\item Hierarchical local grid refinement
>\item Nonconformity in and between levels of refinement
>\item Separation of grids and corresponding degrees of freedom
>\item Overlapping and nonoverlapping decompositions for
> parallel processing
>\end{itemize}
>An implementation of the grid interface may cover only a subset of
>these features.
>
>
>The first formal definition of a grid for numerical computations
>was given by \citet{Berti2000}. He saw clearly that the productivity
>of people working in numerical analysis could be increased greatly by
>the use of reusable components. In particular this meant separating
>the algorithm from the implementation of the grid by specifying a set
>of {\em kernel concepts} of a grid that algorithms should rely on
>exclusively. \citeauthor{Berti2000} used generic programming
>intensively to reduce the interface overhead and also treated the
>problem of data-parallel grid computations.
>
>With applications in numerical relativity in mind, \citet{benger:05}
>generalized the definition of a grid such as to be able to
>handle grids of four-dimensional curved space-time. Inspired by
>differential geometry, he introduced the {\em fiber bundle data model}.
>His grids include sets of local coordinate
>charts which allow the description of curved spaces without a
>surrounding Euclidean space.
>Here as well generic programming is used extensively.
>
>\citet{SCDRC:06} took abstraction into a different direction. They
>introduced the notion of {\em relation-based computations}. This
>very general concept subsumes many different grid operations but
>also algorithms from linear algebra such as matrix-vector
>multiplication. They propose a thin low-level software layer
>intended to structure algorithm-oriented parallel computations
>on this very general concept.
>
>All three approaches differ from DUNE in that they do not contain
>the concept of a {\em grid hierarchy}, which is essential for many
>efficient algorithms such as adaptive local grid refinement or
>geometric multigrid solvers. Also, neither of the implementations
>was designed with the idea in mind that it should be possible to
>reuse legacy code and switch between grid implementations
>quickly. These, however, are central ideas of DUNE.
>
>In our view a grid is a set of entities (the abstraction of vertices,
>edges, elements, etc.) which have certain properties and relations
>to each other. In Section~\ref{Sec:Entities} the entities are formally
>defined together with the subentity relation. Then Sections
>\ref{Sec:Hierarchy} and \ref{Sec:Intersections} introduce the father and the
>intersection relations. These three relations are enough to describe
>the topology of a grid. Section \ref{Sec:Geometry} generalizes the geometric
>properties of entities to arbitrary shapes while Section
>\ref{Sec:Parallelization} introduces the necessary concepts for parallel
>computation on a general grid. Finally, in Section \ref{Sec:Indices}
>we show how data (e.~g., degrees of freedom in the finite element
>context) can be associated with entities of a grid in a general and
>efficient way.
>
>% \section{Grid}\label{Sec:Grid}
>
>% In this section we present the formal definition of a Grid.
>% This definition uses other definition of sets, maps, and relations that are
>% described in the following sections of this paper.
>
>% \begin{defi}[Grid] Formally we define a grid as a tupel
>% $$G=(E,m,\mathcal{S},\mathcal{F},f,\mathcal{I},\mathcal{P},\mathcal{D}).$$
>% $E\subset\mathcal{E}$ is a finite set of entities $E$ out of an
>% infinite set $\mathcal{E}$. The set $\mathcal{E}$ is only used to
>% distinguish individual entities.
>% \oliver{Was genau ist $\mathcal{E}$ und wof\"ur braucht man es?}
>% The entities itself are characterized
>% by various maps and relations defined on $E$.
>% %(one can think of $\mathcal{E}$ being
>% %a set of numbers for the entities, e.~g.~$\mathcal{E}=\mathbb{N}$).
>% The geometric aspects of a grid are given by the geometry map $m$ and the
>% embedding map $f$. The topology of a grid is described by the
>% subentity relation $\mathcal{S}$, the father relation $\mathcal{F}$
>% and the intersection relation $\mathcal{I}$. Finally, the parallel
>% data decomposition is described by the process set $\mathcal{P}$ and
>% the decomposition relation $\mathcal{D}$. These sets, maps and relations are now
>% discussed in detail in the rest of this paper.
>% \oliver{Sonderlich inhaltsreich finde ich diese Definition nicht.}
>% \end{defi}
>
>\section{Entities}\label{Sec:Entities}
>
>In this section we define the basic building blocks of a grid --- the
>entities. Entities are regions of space which satisfy a number of
>additional properties.
>\oliver{Gem\"a\ss{} Def. 5 sind Entities keines 'regions of space' sondern
>rekursiv definierte Mengen von diskreten Punkten.}
>In this section we will mainly discuss
>topological properties, however we need a few basic geometric
>definitions on which these topological properties are built.
>
>\begin{defi}[Convex Polytope]
>A subset $\theta\subset\mathbb{R}^w$, $w\geq 0$, is a convex polytope if it is
>the convex hull of a nonempty finite set of points $X=\{x_0,\ldots,x_n\}$. The
>dimension $\operatorname{dim}(\theta)$ of the convex polytope is
>the maximal number of
>linearly independent vectors in the set $\{x_1-x_0,\ldots,x_n-x_0\}$
>if $n\geq 1$ and $0$ if $n=0$. Obviously, $0\leq \mathrm{dim}(\theta) \leq w$. Given a
>nonempty, finite set of points $X$ we denote by $\theta(X)$ the convex
>polytope generated by $X$.
>\hfill $\square$
>\end{defi}
>
>A common relation of two convex polytopes is one being a face of the
>other which is formally introduced next.
>
>\begin{defi}[Face of a Convex Polytope]
>Let $\theta,\sigma\subset\mathbb{R}^w$ be two convex po\-lytopes
>generated by the point sets $X$ and $Y$ respectively. $\sigma$ is
>called a face of $\theta$ iff
>\begin{itemize}
>\item[(a)] $Y\subseteq X$,
>\item[(b)] $\sigma\cap\mathrm{int}(\theta)=\emptyset$, where
> $\mathrm{int}(\theta)$ denotes the interior of the closed set
> $\theta$,
>\item[(c)] adding any $x\in X\setminus Y$
>to $Y$ would either increase $\mathrm{dim}(\sigma)$ or lead to
>$\sigma\cap\mathrm{int}(\theta)\neq\emptyset$.\hfill $\square$
>\end{itemize}
>\end{defi}
>
>\oliver{Sollte man eventuell $\theta$ als Face von sich selbst zulassen?}
>\robert{Nein, zumindest ist es weiter hinten ausgeschlossen (siehe kurz vor Hierarchy)}
>\robert{Hier ist nicht klar, was man genau will.
>Nach der Definition ist z.B. auch eine Linie die in einer Fl\"ache eine
>Tetraeders verl\"auft, ein Face. Will man das? Wenn nicht muss noch was
>erg\"anzt werden.}
>\oliver{Stimmt nicht. Eine Linie in einer Fl\"ache eines Tetraeders kann
>nicht von einer Punktmenge $Y \subseteq X$ erzeugt sein.}
>
>Based on these definitions we can define the codimension of a
>convex polytope relative to another convex polytope which is central
>to our dimension-independent formalization of a grid.
>
>\begin{defi}[Codimension]
>Let $\theta,\sigma\subset\mathbb{R}^w$ be two convex polytopes with
>$\sigma$ a face of $\theta$. Then
>$\mathrm{codim}(\sigma,\theta) = \mathrm{dim}(\theta)-\mathrm{dim}(\sigma)$ is
>called the codimension of $\sigma$ with respect to $\theta$. Obviously,
>we have $0<\mathrm{codim}(\sigma,\theta)\leq \mathrm{dim}(\theta)$.
>For convenience we extend this definition by
>$\mathrm{codim}(\theta,\theta)=0$. \hfill $\square$
>\end{defi}
>
>\oliver{Ehrlich gesagt finde ich die Konstruktion \"uber die Kodimension unn\"otig
>kompliziert. Sie bietet keinen praktischen Vorteil, aber man mu\ss{} immer noch
>eine Ecke weiter denken.}
>
>We are now in a position to give a formal definition of
>entities. Throughout the rest of the paper $w\in\mathbb{N}$ and
>$d\in\mathbb{N}$ with $d\leq w$ are arbitrary but fixed numbers.
>$d$ will denote the dimension of the grid and $w$ the
>dimension of the Euclidean space the grid is embedded in.
>
>In the following let
>$V\subset \mathbb{N}_0\times \mathbb{N}_0 \times \mathbb{R}^w$ be fixed.
>For any $v=(i,l,x)\in V$ the first component $i$ is an id, the second
>component $l$ denotes the level of the vertex and
>$x$ is the position of the vertex in the Euclidean space.
>The id $i$ is introduced to
>disambiguate vertices that are at the same position and have the same level.
>This is necessary since our grids may be arbitrarily nonconforming.
>
>In the following we define the set $E$ of all possible entities based on the
>vertex set $V$.
>
>\begin{defi}[Entities]\label{Def:Entities}
>The definition is recursive in the codimension $0\leq c \leq d$ where
>$d\in\mathbb{N}_0$ is the fixed dimension. % of the grid.
>
>\begin{enumerate}
>\item We define the set of codimension $d$ entities
> $E^d$ as $$E^d = \left\{ \{v\}\,|\, v\in V \right\}\subseteq\mathcal{P}(V).$$
>Here $\mathcal{P}(\cdot)$ denotes the set of all subsets (power set) of a set.
>Thus, a codimension $d$ entity is a set containing exactly one vertex $v\in V$.
>For any $e\in E^d$, $e=\{(i,l,x)\}$ we define the following maps to
> select components:
>\begin{align*}
>I&:E^d\to\mathbb{N}_0, & I(e)&=i, \\
>L&:E^d\to\mathbb{N}_0, & L(e)&=l, \\
>X&:E^d\to\mathcal{P}(\mathbb{R}^w), & X(e)&=\{x\}.
>\end{align*}
>
>\item For $0\leq c < d$ we define the set of codimension $c$ entities
> as $$E^c\subseteq\mathcal{P}(E^{c+1}),$$ i.e., a codimension $c$ entity
> is a set of codimension $c+1$ entities.
>
> As a first requirement we have that
>\begin{equation*}
>\bigcup_{e\in E^c} e = E^{c+1},
>\end{equation*}
> i.~e., every codimension $c+1$ entity is element of at least
> one codimension $c$ entity.
>
> For any $e\in E^c$ we extend the map $X$ from \ref{enum:point_entities}.) as
>\begin{align*}
>X&:E^c\to\mathcal{P}(\mathbb{R}^w), & X(e)&=\bigcup_{s\in e} X(s).
>\end{align*}
>Intuitively, $X(e)$ is the set of vertices of the entity $e$.
>
>Denote by $\theta_e=\theta(X(e))$ the convex polytope associated with $e$.
>Now any $e\in E^c$ should satisfy the following properties:
>\begin{itemize}
>\item[(i)] We require that $\operatorname{dim}(\theta_e)=d-c$.
> Note that this property holds automatically for $c=d$.
>\item[(ii)] For all $s\in e$, $\theta_s$ is a
> face of $\theta_e$ with $\mathrm{codim}(\theta_s,\theta_e)=1$. The set of
> $\theta_s$ for $s\in e$ cover the boundary of $\theta_e$:
> $$
>\bigcup_{s\in e} \theta_s = \partial \theta_e.
>$$
>\item[(iii)] The entities in $e$ are essentially nonoverlapping,
> i.~e.~$\forall s,s^\prime\in e$, $s\neq s^\prime$, we have
> $$\left\{\begin{array}{ll}
> \theta_s\cap\theta_{s^\prime}=\emptyset & \mathrm{if }\quad c+1=d,\\
> \mathrm{codim}(\theta_s\cap\theta_{s^\prime},\theta_e)\geq 2 &
> \mathrm{if }\quad c+1<d. \end{array}\right.$$ In the first case the
> $s\in e$ consist of single vertices.
>\item[(iv)] $\forall s,s^\prime\in e$ we require $L(s) = L(s^\prime)$.
> Therefore it make sense to define
>\begin{align*}
>L&:E^c\to\mathbb{N}_0, & L(e)&=L(s) \quad \text{for all $s\in e$}.
>\end{align*}
>\end{itemize}
>
>
>\item Finally we define the set of all entities
> $E$, the set of level $j$ entities
> $E_j$ and the codimension $c$ entities
> on level $j$, $E_j^c$:
>\begin{align*}
> E &= \bigcup_{c=0}^d E^c, &
> E_j &= \{ e\in E\,|\, L(e) = j\}, &
> E_j^c &= \{ e\in E^c\,|\, L(e) = j\}.
>\end{align*}
>\end{enumerate}
>Note that with this definition rather general grids can be
>represented. Grids can be nonconforming and entities can be arbitrary
>convex polytopes.\hfill $\square$
>\end{defi}
>
>\begin{figure}
>\begin{center}
>\psfrag{n0}{$v_0$}
>\psfrag{n1}{$v_1$}
>\psfrag{n2}{$v_2$}
>\psfrag{n3}{$v_3$}
>\psfrag{n4}{$v_4$}
>\psfrag{n5}{$v_5$}
>\psfrag{n6}{$v_6$}
>\psfrag{n7}{$v_7$}
>\psfrag{n8}{$v_8$}
>\psfrag{x}{x}
>\psfrag{y}{y}
>\psfrag{2}{2}
>\psfrag{4}{4}
>\psfrag{6}{6}
>\psfrag{8}{8}
>\includegraphics[width=0.6\textwidth]{./EPS/simplegrid.eps}
>\end{center}
>\caption{Graphical representation of the entity set discussed in Example~\ref{Example1}.}
>\label{Fig:SimpleGrid}
>\end{figure}
>
>\begin{exmpl} \label{Example1}
>We show what the entities would be for the simple grid shown in Figure
>\ref{Fig:SimpleGrid}. First, the set of vertices is $V=\{v_0,\ldots,v_8\}$
>with
>\begin{align*}
>v_0 &= (2,2)^T,&
>v_1 &= (4,1)^T,&
>v_2 &= (7,1)^T, \\
>v_3 &= (4,2)^T,&
>v_4 &= (4,3)^T,&
>v_5 &= (7,3)^T, \\
>v_6 &= (4,5)^T,&
>v_7 &= (4,5)^T,&
>v_8 &= (7,5)^T.
>\end{align*}
>\oliver{Da bei uns der hierarchische Aspekt so wichtig ist sollte das Gitter
>vielleicht auch was hierarchisches enthalten?}
>All vertices are on level $0$, i.e., $L(v) = 0 \; \forall v \in V$. Vertices $v_6$,
>$v_7$ are at the same position $(2,4)^T$.
>The dimension of the grid is $d=2$ with world
>dimension $w=2$. The codimension $2$ entities are
>$$
>E^2 =
>\big\{
>\{v_0\}, \ldots, \{v_8\} \big\}.
>$$
>The codimension $1$ entities are
>the edges in the grid which are denoted as
>$$
>E^1=\Big\{
>\big\{\{v_0\},\{v_1\}\big\}, \big\{\{v_1\},\{v_3\}\big\},
>\big\{\{v_0\},\{v_3\}\big\}, \ldots \Big\}.
>$$
>Finally, the codimension $0$ entities are the elements of the grid
>which in our notation are
>\begin{align*}
>\bigg\{
>& \Big\{ \big\{\{v_0\},\{v_1\}\big\}, \big\{\{v_1\},\{v_3\}\big\},
>\big\{\{v_0\},\{v_3\}\big\} \Big\},\\
>&\Big \{ \big\{\{v_0\},\{v_3\}\big\}, \big\{\{v_3\},\{v_6\}\big\},
>\big\{\{v_0\},\{v_6\}\big\} \Big\},\\
>&\Big\{ \big\{\{v_1\},\{v_2\}\big\}, \big\{\{v_2\},\{v_5\}\big\},
>\big\{\{v_4\},\{v_5\}\big\}, \big\{\{v_1\},\{v_4\}\big\} \Big\},\\
>&\Big\{ \big\{\{v_4\},\{v_5\}\big\}, \big\{\{v_5\},\{v_8\}\big\},
>\big\{\{v_7\},\{v_8\}\big\}, \big\{\{v_4\},\{v_7\}\big\} \Big\} \bigg\}.
>\end{align*}
>\hfill $\square$
>\end{exmpl}
>
>\begin{defi}[Subentity relation]
>The definition of entities given above naturally gives rise to
>a binary relation $S\subseteq E\times E$ with
>$$
>e\,S\,e^\prime
>\quad \Leftrightarrow \quad e\in e^\prime.
>$$
>\oliver{Ich finde die Verwendung von Gro\ss buchstaben f\"ur bin\"are Relationen
>sehr unleserlich.}
>By $\mathcal{S}\subseteq E\times E$ we denote the reflexive and transitive closure of this
>relation:
>$$
>e\,\mathcal{S}\,e^\prime
>\quad\Leftrightarrow\quad
>e=e^\prime \vee
>\exists \{e_0,e_1,\ldots,e_k\}
>$$
>with
>$$
>e=e_0, e_k=e^\prime:
>\forall 0\leq i<k: e_i\,S\,e_{i+1}.
>$$
>By $s(e) = \{e^\prime\in E\,|\,
>e^\prime \, \mathcal{S} \, e \}$ we denote the set of all subentities
>of a given entity $e\in E$. \hfill $\square$
>\end{defi}
>
>%\section{Hierarchy}\label{Sec:Hierarchy}
>
>Grids considered in this paper exhibit a hierarchical structure
>obtained from successive refinement. %In this section we describe this
>%hierarchical structure by
>First we define a binary father relation:
>
>\begin{defi}[Father relation]
>Let $F^0\subseteq E^0\times E^0$ be a binary relation on the
>codimension $0$ entities. We have $f\,F^0\,e$ (in
>words: $f$ is the father of $e$) if and only if the following two
>conditions hold:
>\begin{itemize}
>\item[(a)] $\theta_e\subseteq \theta_f$,
>%\robert{F\"ur parametrische R\"ander muss hier noch eine Erg\"anzung hin.}
>\item[(b)] $L(e) = L(f) + 1$.
>\end{itemize}
>Using the father relation we can also define the concept of children:
>$$ c(f) = \{e\in E\,|\, f\,F\,e\}$$
>are the children of $f$, while
>$$ o(f) = \{e\in E\,|\, f\,\mathcal{F}\,e\}$$ is called the set of offsprings of
>$f$.
>
>
>%\andreas{At the moment DUNE does not provide father information
>% for any codim>0 entities. So this definition is prehaps
>% not required? If we want to keep it I wonder if
>% father relations between entities of different codimension
>% is needed? Or do we just need $F^c$ satisfying (a),(b)?}
>
>% The father relation is extended to entities of all codimensions as
>% follows: Set $F\subseteq E\times E$ with $f\,F\,e$ if and only if the
>% following three conditions hold:
>% \begin{itemize}
>% \item[(c)] $\theta_e\subseteq \theta_f$,
>% \item[(d)] There exist codimension 0 entities $f^\prime, e^\prime\in E^0$
>% such that $f^\prime\,F^0\,e^\prime \wedge f\,\mathcal{S}\,f^\prime
>% \wedge e\,\mathcal{S}\,e^\prime$. This last condition is necessary
>% to account for entities covering the same position in space. Note
>% also that $F^0\subseteq F$ due to reflexivity of $\mathcal{S}$.
>% \end{itemize}
>% \oliver{So far this definition allows a father relation between entities of
>% different codimension. (f) prevents this later one. I propose to directly
>% state here that father-son pairs should have the same codimension.}
>% Note that $L(e) = L(f) + 1$ follows from (a) and (d) for entities
>% of nonzero codimension.
>% Let $\mathcal{F}\subseteq E\times E$ denote the transitive
>% closure of the relation $F$. With this notation in place, $f(e) =
>% \{f\in E\,|\, f\,F\,e \}$ is the set of fathers of $e$ (it will follow later
>% from geometrical constraints that $|f(e)|\leq 1$), $c(f) =
>% \{e\in E\,|\, f\,F\,e\}$ are the children of $f$ while $o(f) =
>% \{e\in E\,|\, f\,\mathcal{F}\,e\}$ is called the offspring of
>% $f$.
>
>%\andreas{The following distinguishes a grid and follows in the next section...}
>
>% Finally, the father relation is required to fulfill the following
>% consistency conditions:
>% \begin{itemize}
>% \item[(e)] Only the level $0$ entities do not have a
>% father entity:
>% \begin{equation*}
>% \forall e\in E^c,\ 0 \leq c \leq d : \left( \exists f\in E^c: f\,F\,e
>% \quad\Leftrightarrow \quad L(e)>0 \right),
>% \end{equation*}
>% \item[(f)] and the children cover the father:
>% \begin{equation}
>% \forall e\in E^0 : \bigcup_{s\in c(e)} \theta_s = \theta_e.
>% \label{Eq:VerticalCovering}
>% \end{equation}
>% \oliver{Stimmt nur, wenn keine parametrisierten R\"ander benutzt werden.}
>% \end{itemize}
>\mbox{}\hfill $\square$
>\end{defi}
>
>\begin{defi}[Copies]
>If an entity has exactly one child we call this child a copy of
>its father. We define the reflexive and symmetric binary relation
>$C\subseteq E\times E$ via $$e\,C\, e^\prime \quad
>\Leftrightarrow \quad e=e^\prime\ \vee\ c(e)=\{e^\prime\}\ \vee\
>c(e^\prime)=\{e\}.$$
>The transitive closure $\sim$ of $C$ is an equivalence relation.
>\hfill $\square$
>
>% \begin{defi}[Leaf entities]
>% The set of codimension $c$ leaf entities $L^c\subset E^c$ is defined for
>% $0\leq c\leq d$ recursively over $c$:
>% \begin{enumerate}
>% \item $e\in L^0$ if and only if $e\in E^0$ and $c(e)=\emptyset$.
>% \item $e\in L^c$ if and only if there exists an $e'\in L^0$
>% and $e\mathcal{S}e'$.
>% \end{enumerate}
>
>% The set of entities $E$ together with
>% the father relation $F$ can be interpreted as a forest,
>% where each $e\in E$ with $f(e)=\emptyset$ is the root of
>% a tree formed by $e$ and its offspring $o(e)$.
>% The leaf entities of these trees are important as they constitute the
>% ``finest grid'' available for computations. We generalize the notion
>% of ``leaf'' by defining $L_j\subseteq E$ as the set of leaves of at
>% most level $j\leq J=\max\{L(e)\,|\, e\in E\}$. This is done in
>% a two-step process. First, for codimension $0$
>% we set
>% $$
>% L^0_j = \{e\in E^0 \,|\, L(e)=j \vee (L(e)<j \wedge
>% o(e)=\emptyset) \}
>% $$
>% and then include the remaining codimensions
>% $$L_j = \{ e\in E \,|\, \exists
>% e^\prime\in L^0_j: e\,\mathcal{S}\, e^\prime \}.$$ Due to reflexivity of
>% $\mathcal{S}$ we have $L^0\subseteq L$. The leaf entities (without
>% level index) are then $$L=L_J, \quad J = \max\{L(e)\,|\, e\in E\}.$$
>% \oliver{Wof\"ur braucht man $L_j$?}
>%\mbox{}\hfill $\square$
>\end{defi}
>
>\begin{defi}[Hierarchic Tessillation of a domain $\Omega$]
>
>A subset $T^0$ of $E^0$ is a hierarchic tessillation of $\Omega\subset\mathbb{R}^w$
>if and only if
>$T^0$ satisfies
>\begin{enumerate}
>\item The level zero entities form a non-overlapping partition of $\Omega$
> i.e.,
> \begin{equation}
> \forall e,e^\prime\in T^0, L(e)=L(e')=0: \mathrm{int}(\theta_e) \cap
> \mathrm{int}(\theta_{e^\prime}) = \emptyset.
> \label{Eq:HorizontalPartitioning}
> \end{equation}
> and
> \begin{eqnarray*}
> \bigcup_{e\in T^0, L(e)=0} \theta(e) = \Omega.
> \end{eqnarray*}
>\item Only the level $0$ entities do not have a
> father entity:
> \begin{equation*}
> \forall e\in T^0 : \left( \exists f\in T^0: f\,F\,e
> \quad\Leftrightarrow \quad L(e)>0 \right),
> \end{equation*}
>\item The set $T^0$ is complete in the following set:
> if $e\in T^0$ with $L(e)>0$ then there exists a $f\in T^0$ with
> $f\,F\,e$.
>\item The children form a non-overlapping partition of the father:
> \begin{equation}
> \forall e\in T^0 : \bigcup_{s\in c(e)\cap T^0} \theta_s = \theta_e.
> \label{Eq:VerticalCovering}
> \end{equation}
> and ${\rm int}(\theta(s))\cap{\rm int}(\theta(s')) = \emptyset$
> for all $s\neq s'\in c(e)\cap T^0$.
> %\oliver{Stimmt nur, wenn keine parametrisierten R\"ander benutzt werden.}
>\end{enumerate}
>For the higher co-dimensions we define
>$T^c = \{e'\in E^c \;|\; \exists e\in T^0 \mbox{ with } e\mathcal{S}e'\}$.
>and the closure of the tessilation is given by
>\begin{eqnarray*}
> T=T^0\bigcup_{0 < c\leq d} T^c.
>\end{eqnarray*}
>
>We define the restrictions of the subentity, father, and child relations onto the
>tessilation:
>\begin{eqnarray*}
> \mathcal{S}^T &:=& \mathcal{S} \cap (T\times T), \\
> \mathcal{F}^T &:=& \mathcal{F} \cap (T\times T), \\
> c^T(f) &:=& c(f) \cap T, \\
> o^T(f) &:=& o(f) \cap T.
>\end{eqnarray*}
>\end{defi}
>
>\begin{defi}[Level and Leaf Tessilation]
>
>Given a hierarchic tessilation $T$ of $\Omega$ we define the $l$-level
>tessilation
>as the subset $L_l^T$ of $T$ defined by
>$L_l^{T,c}:=T\cap \{e\in T^c \;|\; L(e) = l\}$ and
>$L_l^T = \bigcup_{0\leq c\leq d} L_l^{T,c}$.
>
>We define the leaf tessilation of co-dimension $0$ entities
>$\Lambda^{T,0} := \{e\in T^0 \;|\; c^T(e)=\emptyset\}$
>and for all $0<c\leq d$ as
>$\Lambda^{T,c} := \{e\in T \;|\; \mbox{there exists an } e'\in \Lambda^{T,0}
> \mbox{ with } e'\mathcal{S}e\}$.
>The leaf tessilation is then defined by
>$\Lambda^T = \bigcup_{0\leq c\leq d} \Lambda^{T,c}$.
>
>Furthermore we define the closure of the level $l$ tessilation as
>$\bar{L}^{T,c}_l := L_l^T \cap \{e\in \Lambda^{T} \;|\; L(e)<l \}$ and
>the level $l$ domain by
>\begin{equation}
> \Theta_l = \bigcup_{e\in \bar{L}^{T,0}_l}
> \theta_e\subset\mathbb{R}^w \label{Eq:HorizontalCovering}
>\end{equation}
>generated by the convex polytopes of the level $l$ leaf tessilation.
>Moreover, we set
> $$\Theta_\Lambda=\bigcup_{e\in \Lambda^{T,0}}
> \theta_e\subset\mathbb{R}^w $$
>\mbox{}\hfill $\square$
>\end{defi}
>
>% In the leaf grid $L$ entities are from different levels in the
>% case of local grid refinement. Moreover, it may contain entities which
>% are copies of one another. \oliver{Das ist im Hinblick auf die vorrangehenden
>% Definitionen ziemlich trivial.}
>% In practice the leaf grid represents a grid
>% without level information which can be formally defined using
>% the equivalence relation $\sim$ \oliver{Was hei\ss t `in practice'?}.
>
>
>% \begin{defi}[Flat leaf grid]
>% \robert{Ich schlage vor das flat leaf view oder leaf view zu nennen.}
>% By $[e] = \{e^\prime\in
>% L\,|\, e^\prime \sim e\}$ we denote the equivalence
>% class of $e$ in $L$ and $\tilde{L} = L/\sim\, = \{[e]\,|\, e\in L\}$
>% denotes the quotient
>% set. The subentity relation $\mathcal{S}$ can be defined naturally on
>% the quotient set as $\tilde{\mathcal{S}} \subseteq \tilde{L} \times
>% \tilde{L}$ with
>% $$\tilde{e}\,\tilde{\mathcal{S}}\,\tilde{e}^\prime\quad\Leftrightarrow\quad
>% \exists e\in \tilde{e},e^\prime\in\tilde{e}^\prime:
>% e\,\mathcal{S}\,e^\prime.$$ $\tilde{L}$ together with the relation
>% $\tilde{\mathcal{S}}$ is the flat leaf grid. \mbox{}\hfill $\square$
>% \end{defi}
>
>\begin{figure}
>\begin{center}
>\psfrag{e0}{$e_{0}$}
>\psfrag{e1}{$e_{1}$}
>\psfrag{e2}{$e_{2}$}
>\psfrag{e3}{$e_{3}$}
>\psfrag{e4}{$e_{4}$}
>\psfrag{e5}{$e_{5}$}
>\psfrag{e6}{$e_{6}$}
>\psfrag{e7}{$e_{7}$}
>\psfrag{e8}{$e_{8}$}
>\psfrag{e9}{$e_{9}$}
>\psfrag{e10}{$e_{10}$}
>\psfrag{e11}{$e_{11}$}
>\psfrag{e12}{$e_{12}$}
>\psfrag{e13}{$e_{13}$}
>\psfrag{e14}{$e_{14}$}
>\psfrag{e15}{$e_{15}$}
>\psfrag{e16}{$e_{16}$}
>\psfrag{e17}{$e_{17}$}
>\psfrag{e18}{$e_{18}$}
>\psfrag{e19}{$e_{19}$}
>\psfrag{e20}{$e_{20}$}
>\psfrag{e21}{$e_{21}$}
>\psfrag{e22}{$e_{22}$}
>\psfrag{e23}{$e_{23}$}
>\psfrag{e24}{$e_{24}$}
>\psfrag{e25}{$e_{25}$}
>\includegraphics[width=0.9\textwidth]{./EPS/twodgridcolor.eps}
>\end{center}
>\caption{Nonconforming nested refinement in a two-dimensional grid.}
>\label{Fig:TwoDGrid}
>\end{figure}
>
>\begin{figure}
>\begin{center}
>\psfrag{e0}{$[e_{0}]$}
>\psfrag{e1}{$[e_{1}]$}
>\psfrag{e2}{$[e_{2}]$}
>\psfrag{e3}{$[e_{3}]$}
>\psfrag{e4}{$[e_{4}]$}
>\psfrag{e5}{$[e_{5}]$}
>\psfrag{e6}{$[e_{6}]$}
>\psfrag{e7}{$[e_{7}]$}
>\psfrag{e8}{$[e_{8}]$}
>\psfrag{e9}{$[e_{9}]$}
>\psfrag{e10}{$[e_{10}]$}
>\psfrag{e11}{$[e_{11}]$}
>\psfrag{e12}{$[e_{12}]$}
>\psfrag{e13}{$[e_{13}]$}
>\psfrag{e14}{$[e_{14}]$}
>\psfrag{e15}{$[e_{15}]$}
>\psfrag{e16}{$[e_{16}]$}
>\psfrag{e17}{$[e_{17}]$}
>\psfrag{e18}{$[e_{18}]$}
>\psfrag{e19}{$[e_{19}]$}
>\psfrag{e20}{$[e_{20}]$}
>\psfrag{e21}{$[e_{21}]$}
>\includegraphics[width=0.9\textwidth]{./EPS/twodgridcolorflattened.eps}
>\end{center}
>\caption{Corresponding flat leaf grid.
>\oliver{Warum werden hier $[e_{15}]$, $[e_{6}]$, $[e_{8}]$, $[e_{11}]$ noch gezeigt?} }
>\robert{Na ja, weil eben genau die zum leaf Gitter geh\"oren.
>\"Ubersichtlicher w\"are es, das linke grobe Element wegzulassen und
>nur die feinen Elemente darzustellen, schliesslich will man ja das flat
>leaf grid zeigen, da haben dann grobe Elemente nichts zu suchen.}
>\oliver{Ich verstehe die Zeichung so, dass $[e_{15}]$ genau dieses linke grobe
>Element ist. Sollte ich mich get\"auscht haben dann ist die Zeichnung zumindest
>missverst\"andlich.}
>\label{Fig:TwoDGridFlattened}
>\end{figure}
>
>\begin{exmpl} \label{Example2}
>The definitions of the leaf tessilation is illustrated with a small
>example. Figure \ref{Fig:TwoDGrid} shows a hierarchical tessilation with
>non-conforming local refinement (``hanging node
>refinement''). Codimension $0$ entities (elements) are shown in red,
>codimension $1$ entities (edges) are shown in green and codimension
>$2$ entities (vertices) are shown in blue. The father relation
>$\mathcal{F}$ is indicated by the black arrows.
>\andreas{again: do we need father relations of codim$>0$ entities?}
> The equivalence
>relation~$\sim$ identifies vertex $e_1$ with vertex $e_{23}$, vertex $e_4$ with
>vertex $e_{25}$ and so forth.
>The flat leaf grid formed by the equivalence classes is
>shown in Figure \ref{Fig:TwoDGridFlattened}. Note that edges
>$e_9, e_{13}, e_{14}$ are all represented by separate
>equivalence classes while vertices $e_1,
>e_{23}$ are represented by a single equivalence class. The same holds
>for vertices $e_4,e_{25}$. \hfill $\square$
>\end{exmpl}
>
>% \begin{defi}[Domain]
>% Let $j \in \mathbb{N}$. Based on our hierarchical construction of grids we
>% define the
>% point sets
>% \begin{equation}
>% \Theta_j =
>% \bigcup_{e\in L_j^0}
>% \theta_e\subset\mathbb{R}^w
>% \label{Eq:HorizontalCovering}
>% \end{equation}
>% generated by the convex polytopes of level $j$ leaf entities.
>% Moreover, we set
>% $$\Theta=\Theta_J.$$ \mbox{}\hfill $\square$
>% \end{defi}
>
>% \begin{defi}[Horizontal Partitioning Property]
>% The purpose of the entities is to partition a domain.
>% Therefore we require that for all level $j$, $0\leq j\leq J$ the
>% following holds:
>% \begin{equation}
>% \forall e,e^\prime\in L^0_j: \mathrm{int}(\theta_e) \cap
>% \mathrm{int}(\theta_{e^\prime}) = \emptyset.
>% \label{Eq:HorizontalPartitioning}
>% \end{equation}
>% \oliver{Falls $d\ne w$ ist hier das relative Innere gemeint.}
>% Together with (\ref{Eq:HorizontalCovering}) this means that the
>% polytopes from $L_j^0$ form a nonoverlapping partitioning of the
>% domain $\Theta_j$ for each level. Together with
>% (\ref{Eq:VerticalCovering}) we also have that the children form a
>% partitioning of their father entity.
>% \oliver{Folgt das nicht automatisch?}
>% \hfill$\square$
>% \end{defi}
>
>
>\section{Intersections}\label{Sec:Intersections}
>
>Many numerical methods require information about intersections of neighboring
>elements. Together with the subentity relation $\mathcal{S}$ and the father
>relation $\mathcal{F}^T$ the intersection relations $\mathcal{I}_l$ and
>${\mathcal{I}_\Lambda}$ provide all information about a grid that is
>needed for implementing numerical schemes on a grid. % in the sequential case.
>
>\begin{defi}[Level Intersections]
>Given a hierarchic tessilation $T$
>we define the ternary level intersection relation
>$\mathcal{I}_l\subseteq L^{T,0}_l
> \times
> (L^{T,0}_l \cup \{\emptyset\})
> \times\mathcal{P}(\mathbb{R}^w)$
>for $l\in\mathbb{N}_0$ as follows:
>\begin{itemize}
>\item[(a)] For any tripel $(e,e^\prime,\theta)\in\mathcal{I}$ we require
> that $e\neq e^\prime$,
> $\theta$ is a convex polytope with $\mathrm{dim}(\theta)=d-1$,
> and one of the following conditions holds:
>\begin{itemize}
>\item[(i)] $e^\prime\neq \emptyset$ then
> $\theta\subseteq\theta_e\cap\theta_{e^\prime}$ or
>\item[(ii)] $e^\prime=\emptyset$
> then $\theta\subseteq\theta_e\cap\partial\Theta_{L(e)}$.
>\end{itemize}
>\item[(b)] The level intersection relation is symmetric with respect to the
> first two arguments:
> $(e,e^\prime,\theta)\in\mathcal{I}_l
> \Rightarrow(e^\prime,e,\theta)\in\mathcal{I}_l$.
>\item[(c)] For any two $e,e^\prime\in T^0$, $e\neq e^\prime$, we have
> $$\bigcup_{(e,e^\prime,\theta)\in\mathcal{I}_l} \theta =
> \theta_e\cap\theta_{e^\prime}$$ and for any $e\in T^0$ we require
> $$\bigcup_{(e,\emptyset,\theta)\in\mathcal{I}_l} \theta =
> \theta_e\cap\partial\Theta_{L(e)}.$$
>\item[(d)] For any two $(e,e^\prime,\theta^\prime),
> (e,e^{\prime\prime},\theta^{\prime\prime})\in\mathcal{I}_l$ we have
> $\mathrm{dim}(\theta^\prime\cap\theta^{\prime\prime})<d-1$, i.~e.~the
> intersections of one entity are essentially non-overlapping.
>\end{itemize}
> \mbox{}\hfill$\square$
>\end{defi}
>Note that for fixed $e, e' \in T^0$, there may be more than one $\theta$
>with $(e,e',\theta) \in \mathcal{I}_l$. The reason is to allow implementations
>to split element intersections $\theta_e \cap \theta_{e'}$ into several
>parts. It is then generally easier to integrate over the parts separately rather
>than integrating about the intersection as a whole.
>
>A similar definition is now given for the leaf tessilation $\Lambda^T$.
>
>\begin{defi}[Leaf Intersections]
>We define the ternary leaf intersection relation
>$\mathcal{I}_\Lambda\subseteq
>\Lambda^T\times(\Lambda^T\cup\{\emptyset\})\times\mathcal{P}(\mathbb{R}^w)$ as
>follows:
>\begin{itemize}
>\item[(a)] For any tripel
> $(e,e^\prime,\theta)\in\mathcal{I}_\Lambda$ we require that $e\neq e^\prime$,
> $\theta$ is a convex polytope with $\mathrm{dim}(\theta)=d-1$,
> and one of the following conditions holds
>\begin{itemize}
>\item[(i)] $e^\prime\neq \emptyset$ then
> $\theta\subseteq\theta_e\cap\theta_{e^\prime}$ or
>\item[(ii)] $e^\prime= \emptyset$ then $\theta\subseteq\theta_e\cap\partial\Theta_\Lambda$.
>\end{itemize}
>\item[(b)] The leaf intersection relation is symmetric with respect to the
> first two arguments:
> $(e,e^\prime,\theta)\in\mathcal{I}_\Lambda\Rightarrow(e^\prime,e,\theta)
> \in\mathcal{I}_\Lambda$.
>\item[(c)] For any $e\in\Lambda^T$ we require
> $$
>\bigcup_{(e,e^\prime,\theta)\in\mathcal{I}_\Lambda} \theta =
> \partial \theta_e,
>$$
>i.~e., all intersections
> of an entity cover its boundary. Note that such a condition is not
> valid for the level intersections because of local hierarchical
> refinement. \oliver{Das ist in der Implementierung aber nicht so!}
> \andreas{zum teil schon...}
>\item[(d)] For any two $(e,e^\prime,\theta^\prime),
> (e,e^{\prime\prime},\theta^{\prime\prime})\in\mathcal{I}_\Lambda$ we have
> $\mathrm{dim}(\theta^\prime\cap\theta^{\prime\prime})<d-1$, i.~e.~the
> intersections of one entity are essentially non-overlapping.
>\end{itemize}
> \mbox{}\hfill$\square$
>\end{defi}
>
>\section{Geometry}\label{Sec:Geometry}
>
>So far all entities represented convex polytopes. In order to allow
>entities to represent more complex shapes we introduce the following
>
>\begin{defi}[Curved Entities]
>With every entity $e\in T^0$ we associate a map $m_e : \theta_e \to
>\mathbb{R}^w$ and set $\omega_e = \mathrm{range}(m_e)$ to be the
>transformed polytope associated with $e$. The maps are required to
>fulfill the following properties:
>\begin{itemize}
>\item[(a)] For all $e\in T^0$, $m_e$ is a continuously differentiable one-to-one
> function.
>\item[(b)] For all $e\in T^0$, we have $\forall x\in X(e): m_e(x) = x$. This
> ensures that $\theta_e$ is an approximation of $\omega_e$.
>\oliver{Approximation in welchem Sinne? Und wof\"ur brauchen wir diese
>Eigenschaft eigentlich?}
>\item[(c)] The transformed domains $\Omega_j$ are defined for
> $l\in\mathbb{N}$
> as $$\Omega_l = \bigcup_{e\in
> \Lambda_l^{T,0}} \omega_e.$$
>\item[(d)] The transformed polytopes are nonoverlapping on all leaf
> tessilations, i.~e., for all $l\in\mathbb{R}$,
> the following is
> true: $$\forall e,e^\prime\in
> \Lambda_l^{T,0}: (e\neq e^\prime) \Rightarrow
> \mathrm{int}(\omega_e)\cap\mathrm{int}(\omega_{e^\prime})=\emptyset.$$
>\oliver{Falls $d \ne w$ ist hier das relative Innere gemeint}.
>\end{itemize}
>For subentities we define the corresponding maps as restrictions of
>the co-dimension $0$ mappings:
>$$ m_s = m_{e{|s}} \quad\mbox{for}\quad s\mathcal{S}e $$
>
>It follows that maps
>on intersections are consistent:
>$$\forall (e,e^\prime,\theta)\in\mathcal{I},
> \forall x\in\theta : m_e(x)=m_{e^\prime}(x).$$
> \mbox{}\hfill$\square$
>\end{defi}
>
>\begin{rem}[Reference Elements]
>Typical grids contain only entities derived from a few different shapes,
>e.~g.~simplices or cubes. Moreover, efficient numerical integration is
>only possible for certain standard shapes. Therefore, in practice one
>will generate the entities $e\in E$ through transformations from
>templates, so-called reference elements.
>In general there exists a finite set $\hat{\Theta}$ consisting of
>co-dimension $0\leq c\leq d$ polytopes so that for each $e\in E^c$
>there exists a $\hat{\theta}\in \hat{\Theta}$ and a transformation
>$$
>\hat{m}_e :\hat{\theta}\to\theta_e.
>$$
>For efficiency reasons it is also advantageous to directly
>provide the combined transformation $\hat{m}^\prime = m \circ
>\hat{m}$.
>\andreas{We do have reference elements in DUNE...}
>Reference elements are not part of our general description of grids, though.
>\end{rem}
>
>\section{Parallelization}\label{Sec:Parallelization}
>
>We assume that parallel computations on a grid follow the `single
>program multiple data' (SPMD) programming paradigm based on a suitable
>data \oliver{Wieso `data'?} decomposition of the grid entities.
>
>The data decomposition is carried out in a two step process. First,
>codimension 0 entities are assigned to processes (master
>decomposition). In a second step the data decomposition for the
>remaining entities is determined from this master decomposition.
>We assume that $n \geq 1$ processes are available for the parallel
>computation and that each process is identified by a number
>$p \in P=\{0,\ldots,n-1\}$. In the following a fixed hierarchic
>tessilation $T^0$ is given. Then we define a data decomposition.
>
>\begin{defi}[Master Data Decomposition]
>The master data decomposition is then defined
>as follows:
>\begin{enumerate}
>\item[(a)] The mapping of entities to processes is described by the master data
>decomposition relation $$\mathcal{D}^0\subseteq T^0\times P.$$ If
>$e\,\mathcal{D}^0\,p$ then entity $e$ is known to process $p$.
>
>\item[(b)] The map $$t^0 : \mathcal{D}^0 \to \{i,o,g\}$$ assigns a partition
> type $t(e,p)$ to entity $e$ in process $p$. The three partition
> types are called interior ($i$), overlap ($o$) and ghost ($g$).
>
>\item[(c)] Using these definitions we introduce the following notation:
>\begin{align*}
>E^0|_p^\tau &= \{e\in T^0\,|\, (e,p)\in\mathcal{D} \wedge t(e,p)=\tau\}, &
>E^0|_p &= \bigcup_{\tau\in\{i,o,g\}} E^0|_p^\tau
>\end{align*}
>\end{enumerate}
>We now assume that the relation $\mathcal{D}$ and the mapping $t$ fulfill
>the following properties:
>\begin{enumerate}
>\item $T^0 = \bigcup_{p\in P} E^0|_p^i$.
>
>% and require that the interior codimension $0$ entities $E^0|_p^i$ form a partition
>% of the entity set:
>% \begin{align*}
>% \bigcup_{p\in P} E^0|_p^i &= E^0, &
>% E^0|_p^i \cap E^0|_q^i = \emptyset \ \text{ for all }\ p\neq q.
>% \end{align*}
>
>\item Set $\mathcal{F}^0|_p = \mathcal{F}^T\cap (E^0|_p \times E^0|_p)$.
> We require that the father relation $\mathcal{F}^T$ on $T^0$ can be
> represented in a distributed way. This means that $\bigcup_{p\in P}
> \mathcal{F}^0|_p = \mathcal{F}^T$. In order to ensure this we postulate:
>\begin{equation*}
>e\,\mathcal{D}^0\,p \wedge t(e,p)\in\{i,o\} \wedge
> f\,\mathcal{F}\,e \,\Rightarrow\, f\,\mathcal{D}^0\,p.
>\end{equation*}
>A consequence of this is that if father and child are in different
>processes, the father must be introduced as a ghost entity in the
>child's process.
>
>\item A similar requirement is needed in order to represent each
> intersection in at least one process. Here we require more
> flexibility, however, because overlapping and nonoverlapping
> decompositions are useful in practice.
>
> %One possibility is the following requirement
> Therefore we require:
>\begin{equation} \label{Eq:IntersectionGhosts}
>e\,\mathcal{D}^0\,p \wedge t(e,p)=i \wedge
> (e,e^\prime,\theta)\in\mathcal{I} \,\Rightarrow\, e^\prime\,\mathcal{D}^0\,p
>\end{equation}
>where $\mathcal{I}=\mathcal{I}_l,\mathcal{I}_\Lambda$.
>This means that the interior entities are surrounded by at least one
>layer of entities which are either overlap or ghost (or both).
>%\oliver{You cannot meditate about ``possibilities'' in a definition!!!}
>
>%Another option is to skip (\ref{Eq:IntersectionGhosts})
>%altogether. This would allow as a smallest possible partition $E^0|_p
>%= E^0|_p^i$, i.~e.~interior codimension $0$ entities only.
>\end{enumerate}
> \mbox{}\hfill$\square$
>\end{defi}
>The purpose of the partition type is to define
> subdomains for each process $p$ and refinement level $j$ via
>\begin{align*}
>I_{j,p} &= \bigcup_{e\in E^0|_p^i} \theta_e, &
>O_{j,p} &= \bigcup_{e\in E^0|_p^o} \theta_e, &
>G_{j,p} &= \bigcup_{e\in E^0|_p^g} \theta_e.
>\end{align*}
>These subdomains are illustrated in Figure
>\ref{Fig:DataDecomposition}. The $I_{j,p}$ are nonoverlapping by
>definition. Then $O_{j,p}$ is intended to ``surround'' $I_{j,p}$, and
>$G_{j,p}$ in turn ``surrounds'' $O_{j,p}$. Note here that overlap
>and/or ghost entities may not exist at all. In this case the
>corresponding subdomains are empty.
>
>
>
>\begin{figure}
>\begin{center}
>\psfrag{om}{$\Omega$}
>\psfrag{dom}{$\partial\Omega$}
>\psfrag{omi}{$I_{j,p}$}
>\psfrag{omo}{$O_{j,p}$}
>\psfrag{omg}{$G_{j,p}$}
>\psfrag{gb}{$B_{j,p}$}
>\psfrag{gf}{$F_{j,p}$}
>\includegraphics[width=0.7\textwidth]{./EPS/datadecomposition.eps}
>\end{center}
>\caption{Data decomposition based on domain decomposition ideas.}
>\label{Fig:DataDecomposition}
>\end{figure}
>
>
>Up to now, only the decomposition of codimension $0$ entities has been
>handled. The next definition extends the data decomposition relation
>to higher codimensions. We begin by introducing the border and front
>boundaries. We
> define the border boundary as the following part of $\partial I_{p,j}$:
> $$B_{j,p} = \overline{\partial I_{j,p}\setminus\partial\Theta_j}.$$
> Here $\overline{\ \cdot\ }$ denotes the closure of a point set.
> The front boundary is defined as part of $\partial O_{j,p}$ as follows:
> $$F_{j,p} = \left(\overline{\partial
> O_{j,p}\setminus\partial\Theta_j}\right)\setminus B_{j,p}.$$
>These boundaries are also illustrated in Figure
>\ref{Fig:DataDecomposition}. Note that due to this construction the
> points ``$\blacksquare$'' and ``$\circ$'' are
>part of border $B_{j,p}$ and point ``$\square$'' is part of front
> $F_{j,p}$. Note also that these definitions work when overlap
> entities are missing (then the front boundary is empty) or ghost entities are
> missing or both are missing.
>
>\begin{defi}[Extended Data Decomposition]
>The extended data decomposition relation is now
> $$\mathcal{D}\subseteq T\times P$$ and it is derived via the
> subentity relation:
>\begin{equation} \label{Eq:SubentityLocal}
>\forall e\in T^0, \forall s\in T, \forall p\in P: \ s\,\mathcal{S}\, e
>\quad\Rightarrow\quad (s\,\mathcal{D}\, p \ \Leftrightarrow\ e\,\mathcal{D}^0\,p)
>\end{equation}
>i.~e.~an entity and all its subentities are always present together in
>a process. Due to reflexivity of $\mathcal{S}$ we have
>$\mathcal{D}^0\subseteq\mathcal{D}$. Another consequence of
>(\ref{Eq:SubentityLocal}) is that the subentity relation can be
>represented in the distributed data model, i.~e.~
>\begin{align*}
>\bigcup_{p\in P} \mathcal{S}|_p &= \mathcal{S}^T, \mbox{ with } &
>\mathcal{S}|_p &:= \mathcal{S}\cap(E|_p \times E|_p), &
>E|_p &:= \{e\in T\,|\, e\,\mathcal{D}\,p \}.
>\end{align*}
>
>Partition types are generalized to higher codimension with the
> map $$t : \mathcal{D} \to \{i,b,o,f,g\}.$$
>In an abuse of notation we use the symbol $t$ again.
>Two more partition types,
> border ($b$) and front ($f$), are introduced which correspond to the
> boundaries $B_{j,p}$ and $F_{j,p}$ of the subdomains,
> respectively. For any $(e,p)\in\mathcal{D}$ the partition type is
> defined geometrically using the subdomains and boundaries defined above:
>\begin{equation*}
>t(e,p) = \begin{cases}
>i \quad & \text{if $\mathrm{int}(\theta_e) \subseteq \overline{I_{L(e),p}}\setminus B_{L(e),p}$}\\
>b \quad & \text{if $\theta_e \subseteq B_{L(e),p}$}\\
>o \quad & \text{if $\mathrm{int}(\theta_e) \subseteq
>\overline{O_{L(e),p}}\setminus (B_{L(e),p}\cup F_{L(e),p}$}\\
>f \quad & \text{if $\theta_e \subseteq F_{L(e),p}$}\\
>g \quad & \text{if $\mathrm{int}(\theta_e) \subseteq
>\overline{G_{L(e),p}}\setminus (B_{L(e),p}\cup F_{L(e),p}$}
>\end{cases}
>\end{equation*}
>\oliver{Hier braucht man wohl wieder das relative Innere}
>Note that in case $\theta_e$ is a single point $\theta_e=\{x\}$ we
>use the definition $\operatorname{int}(\{x\}) = \{x\}$ for the interior.
>\oliver{Es ist aber eigentlich $\operatorname{int}\{x\} = \emptyset$!}
>Moreover,
>for codimension $0$ entities we have $t(e,p)=t^0(e,p)$.
> \mbox{}\hfill$\square$
>\end{defi}
>
>We now define the grid.
>\begin{defi}[Grid]
>For a given hierarchic tessilation $T$ and extended data decomposition
>$\mathcal{D},t$ a grid on the processor $p\in P$ is now defined as
>$G_p = \{E|p,t|p\}$ with
>$t|p(e) = t(e)$ for all $e\in E|p$.
>\andreas{Somewhat trivial... could be extended by the restriction of
> F,S,I onto the subset of entities.}
>\end{defi}
>
>\begin{rem}[Data Exchange] \label{con:data}
>Besides the data decomposition the data exchange is an important part
>of any parallel algorithm. In our concept this means that data
>associated with the same entity in different processes is to be
>exchanged, and any parallel grid implementation has to support this.
>Formally this can be described as follows. In each process $p \in P$
>select a set of source entities
>$$
>\Sigma_p \subseteq E|_p
>$$
>and a set of destination entities
>$$
>\Delta_p \subseteq E|_p.
>$$
>Then a general communication operation moves
>data for each $e\in\Sigma_p\cap\Delta_p$
>\oliver{Sollte das zweite Argument nicht $q$ sein statt $p$?}
>from process $p$ to process $q\neq p$.
>
>As an example consider an overlapping domain decomposition algorithm
>with piecewise linear finite elements on the finest grid level $J$. In
>that case one would utilize
>\begin{align*}
>\Sigma_p & = E_J^d|_p^i \cup E_J^d|_p^b \cup E_J^d|_p^o &
>\Delta_p & = E_J^d|_p^i \cup E_J^d|_p^b \cup E_J^d|_p^o \cup E_J^d|_p^f.
>\end{align*}
> \mbox{}\hfill$\square$
>
>\oliver{Das finde ich etwas kurz. Man k\"onnte z.B. erw\"ahnen, da\ss{} overlap und
>ghost genau f\"ur diesen Datenaustausch definiert worden sind.}
>\end{rem}
>
>
>
>\section{Indices}\label{Sec:Indices}
>\label{sec:indexsets}
>
>An important part of our concept is that grids are completely separated
>from any numerical data associated with it. However, in order to access the data of
>a grid some link is needed between grid entities and the data. This
>link is provided by the index maps introduced in this section.
>
>Since we like to consider adaptive grid refinement a computation
>actually uses a sequence of different grids rather than a single
>grid. In our concept we assume that a computation consists of
>alternating phases of work to be done on a fixed grid and grid
>modification (refinement, coarsening, or load-balancing). This is reflected by the
>following definition.
>
>\begin{defi}[Grid Sequence]\label{con:gridseq}
>An adaptive computation produces a sequence of entity sets $$\leftidx{^0}{E}{},
>\leftidx{^1}{E}{}, \ldots, \leftidx{^k}{E}{}, \ldots.$$
>The sequence meets the following properties:
>\begin{enumerate}
>\item[(a)] Every $\leftidx{^k}{E}{}$, $k\in\mathbb{N}_0$ is based on the
> same vertex set $V$ (see definition \ref{Def:Entities}) and has the
> same dimension $d$. $V$ is chosen large enough to hold all positions
>\oliver{Aber es darf doch keine Knoten geben, die in keinem Element auftauchen! Def. 4c!}
> occuring in the grid sequence.
>\item[(b)] The coarsest grid level does not change:
> $\leftidx{^{k+1}}{E_0}{}=\leftidx{^k}{E_0}{}$.
>\item[(c)] $\leftidx{^{k+1}}{E}{}$ is obtained from
> $\leftidx{^{k}}{E}{}$ through hierarchic refinement and/or
> coarsening. \oliver{Das finde ich zu ungenau.}
>\end{enumerate}
>For each $k\in\mathbb{N}_0$ the corresponding relations
> $\leftidx{^k}{\mathcal{S}}{}, \leftidx{^k}{\mathcal{F}}{},
> \leftidx{^k}{\mathcal{I}}{}, \leftidx{^k}{\tilde{\mathcal{I}}}{},
> \leftidx{^k}{\mathcal{D}}{}$ and the map $\leftidx{^k}{t}{}$ are
> defined accordingly.
> \hfill$\square$
>\end{defi}
>
>The association of entities with arbitrary user data is achieved by
>associating several indices with each entity. These indices can then be
>used to locate the data in an appropriate data structure, e.~g.~an
>array or a map (associative array).
>We now introduce three different index maps.
>
>\begin{defi}[Level Index Maps] \label{Def:LevelIndexMap}
>For a given sequence index $k$, codimension $c$, level $j$, and process
>number $p$ the level index is a map $$\leftidx{^{k}}{\kappa}{}_j^c|_p :
>\leftidx{^{k}}{E}{}_j^c|_p \to \mathbb{N}_0.$$
>The level index map is consecutive, which means that it is injective and
>$$
>0\leq \leftidx{^{k}}{\kappa}{}_j^c|_p(e) <
> \big\lvert\leftidx{^{k}}{E}{}_j^c|_p\big\rvert \quad \text{for all $e\in
> \leftidx{^{k}}{E}{}_j^c|_p$}.
>$$
>\oliver{Das stimmt nicht ganz mit der Implementierung \"uberein. Dort
>wird noch nach dem GeometryType unterschieden.}
>The level index maps are used to store data in arrays for efficient
>processing. From the individual maps $\leftidx{^{k}}{\kappa}{}_j^c|_p$ one
>can easily construct consecutive maps for unions of sets
>$\bigcup_{c\in C^\prime} \bigcup_{j\in J^\prime}
>\leftidx{^{k}}{E}{}_j^c|_p$.
> \mbox{}\hfill$\square$
>\end{defi}
>
>
>\begin{defi}[Leaf Index Map]
>For a given sequence index $k$ and process
>number $p$ the leaf index map $$\leftidx{^{k}}{\lambda}{} :
>\leftidx{^{k}}{L}{} \to \mathbb{N}_0$$ maps leaf entities to
>consecutive numbers, i.~e.~for all $k\in\mathbb{N}_0$ we require:
>\begin{enumerate}
>\item[(a)] (Range restricted to number of equivalence classes)
>\begin{equation*}
>\forall e\in\leftidx{^{k}}{L}{}: 0\leq \leftidx{^{k}}{\lambda}{}(e) <
> |\leftidx{^{k}}{\tilde{L}}{}|_p|,
>\end{equation*}
>\oliver{Mu\ss{} hier nicht auch nach Entity-Dimension unterschieden werden?}
>\oliver{In der Implementierung wird noch nach dem GeometryType unterschieden.}
>
>\item[(b)] (equality on equivalence classes)
>\begin{equation*}
>\forall e,e^\prime\in\leftidx{^{k}}{L}{} : \leftidx{^{k}}{\lambda}{}(e) =
> \leftidx{^{k}}{\lambda}{}(e^\prime)\,\Leftrightarrow\, [e] = [e^\prime].
>\end{equation*}
>
>\end{enumerate}
> \mbox{}\hfill$\square$
>\end{defi}
>
>
>\begin{defi}[Global Leaf Index Map]
>For a given sequence index $k$ the global leaf index map has the
>signature $$\leftidx{^{k}}{\mu}{} : \leftidx{^{k}}{L}{} \to
>\mathbb{N}_0.$$ The global leaf index maps are required to
>fulfill the property of persistence which is given by the following
>two conditions for every $k\in\mathbb{N}_0$:
>\begin{enumerate}
>\item[(a)] (persistence of index)
>\begin{equation*}
>\forall e\in\leftidx{^{k}}{L}{},
>\forall e^\prime\in\leftidx{^{k+1}}{L}{} : \ e=e^\prime
>\,\Leftrightarrow\, \leftidx{^{k}}{\mu}{}(e) =
>\leftidx{^{k+1}}{\mu}{}(e^\prime),
>\end{equation*}
>
>\item[(b)] (equality on equivalence classes of the same grid)
>\begin{equation*}
>\forall e,e^\prime\in\leftidx{^{k}}{L}{} : \
>\leftidx{^{k}}{\mu}{}(e) = \leftidx{^{k}}{\mu}{}(e^\prime)
>\,\Leftrightarrow\, [e]=[e^\prime]
>\end{equation*}
>\end{enumerate}
>These properties imply that if an entity is contained in two
> subsequent grids the global leaf index does not change. If, however,
> $e\in\leftidx{^{k}}{L}{}$ and $e\in\leftidx{^{k+2}}{L}{}$ but
> not $e\in\leftidx{^{k+1}}{L}{}$ then the entity may have
> a different global index in $\leftidx{^{k}}{L}{}$ and
> $\leftidx{^{k+2}}{L}{}$.
> \hfill$\square$
>\end{defi}
>\oliver{Gibt es also globale Indices nur auf dem Blattgitter? Das ist in
>der Implementierung anders.}
>
>\begin{rem}[Use of Index Maps] Computations on mesh sequences are assumed to be
> structured into alternating phases of work on a fixed grid and
> modifications of the grid to obtain the next grid in the sequence.
>While working on a fixed grid the level and
> leaf indices are used to access data in arrays with constant
> time complexity for each access. In the modification phase the global
> leaf index is used to transfer data from one grid to the next
> grid. During that phase data is typically stored in an intermediate
> data structure with logarithmic time complexity for each access.
> \mbox{}\hfill$\square$
>\end{rem}
>
>\section{Conclusions and Future Work}
>
>In this paper we have given a mathematically rigorous description of general
>grids in Euclidean spaces with arbitrary dimension including elements of
>various shapes, nonconformity,
>hierarchical local refinement, and parallel data decomposition. This
>description provides the foundation for an abstract grid interface
>realized as C++ classes as part of the
>``Distributed and Unified Numerics Environment'' \cite{duneweb}.
>A description of this interface and its implementation is given in the
>companion paper \cite{gridpaper_part2}.
>
>The grids covered by our formal description consist of sets of
>elements which are nonoverlapping on each processor.
>The dimensionality of the elements is arbitrary but
>equal for all elements in one grid. If overlapping grids or grids with
>elements of mixed dimension are required this is currently possible by
>employing different grid objects and coupling them together. A
>relaxation of these restrictions opens up one way for future developments
>of the abstract interface.
>
>\bibliographystyle{plainnat}
>\bibliography{gridmodule}
>
>\end{document}
>
>
>
>------------------------------------------------------------------------
>
>_______________________________________________
>Dune mailing list
>Dune at dune-project.org
>http://lists.dune-project.org/mailman/listinfo/dune
>
>
--
************************************************************************
* Oliver Sander ** email: sander at mi.fu-berlin.de *
* Freie Universität Berlin ** phone: + 49 (30) 838 75217 *
* Institut für Mathematik II ** URL : page.mi.fu-berlin.de/~sander *
* Arnimallee 6 ** -------------------------------------*
* 14195 Berlin, Germany ** Member of MATHEON (www.matheon.de) *
************************************************************************
More information about the Dune
mailing list