grid-howto.tex 112 KB
Newer Older
1
\documentclass[11pt,a4paper,headinclude,footinclude,DIV16,normalheadings]{scrreprt}
Peter Bastian's avatar
Peter Bastian committed
2 3 4 5 6 7 8
\usepackage[automark]{scrpage2}
\usepackage[ansinew]{inputenc}
%\usepackage{german}
%\usepackage{bibgerm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{theorem}
9
\usepackage{xspace}
Peter Bastian's avatar
Peter Bastian committed
10 11 12
\usepackage{color}
\usepackage{listings}
\lstset{language=C++, basicstyle=\ttfamily, 
13 14
  keywordstyle=\color{black}\bfseries, tabsize=4, stringstyle=\ttfamily,
  commentstyle=\it, extendedchars=true, escapeinside={/*@}{@*/}}
Peter Bastian's avatar
Peter Bastian committed
15 16
\usepackage{hyperref}
\usepackage{psfrag}
Peter Bastian's avatar
Peter Bastian committed
17
\usepackage{makeidx}
Peter Bastian's avatar
Peter Bastian committed
18 19 20 21 22 23 24 25 26 27

\usepackage{graphicx}

\DeclareGraphicsExtensions{.eps, .jpg}

\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
28
\newcommand{\Dune}{{\sf\bfseries DUNE}\xspace}
Peter Bastian's avatar
Peter Bastian committed
29 30 31 32

%The theorems
\theorembodyfont{\upshape}
\theoremheaderfont{\sffamily\bfseries}
Oliver Sander's avatar
Oliver Sander committed
33
\newtheorem{exc}{Exercise}[chapter]
Peter Bastian's avatar
Peter Bastian committed
34 35
\newtheorem{rem}[exc]{Remark}
\newtheorem{lst}{Listing}
Peter Bastian's avatar
update  
Peter Bastian committed
36
\newtheorem{warn}[exc]{Warning}
Peter Bastian's avatar
Peter Bastian committed
37 38 39

\pagestyle{scrheadings}

40
\title{The Distributed and Unified Numerics Environment (\Dune{}) Grid
Peter Bastian's avatar
Peter Bastian committed
41
  Interface HOWTO}
42

Martin Nolte's avatar
Martin Nolte committed
43 44
\input{config.tex}

45 46 47 48
\author{Peter Bastian$^\ast$ \and 
Markus Blatt$^\ast$ \and
Andreas Dedner$^\dagger$ \and 
Christian Engwer$^\ast$ \and  
49
Robert Kl\"ofkorn$^\dagger$ \and 
Martin Nolte's avatar
Martin Nolte committed
50 51
Martin Nolte$^\dagger$ \and
Mario Ohlberger$^\mathparagraph$ \and  
52 53
Oliver Sander$^\ddagger$}

Martin Nolte's avatar
Martin Nolte committed
54
\date{Version \version, \today}
Peter Bastian's avatar
Peter Bastian committed
55

56
\publishers{%
Peter Bastian's avatar
Peter Bastian committed
57
\vspace{10mm}
58 59 60 61 62
%\includegraphics[width=0.32\textwidth]{EPS/alberta2d-view2}\hfill
\includegraphics[width=0.32\textwidth]{EPS/ug2dtri-view2}\hfill
\includegraphics[width=0.32\textwidth]{EPS/adaptiveintegration_alberta2d}\hfill
\includegraphics[width=0.32\textwidth]{EPS/alucube3d}
%\includegraphics[width=0.32\textwidth]{EPS/ug2dquad-view2}
Christian Engwer's avatar
Christian Engwer committed
63
\\
Peter Bastian's avatar
Peter Bastian committed
64
\vspace{10mm}
65
{\normalsize $^\ast$Abteilung `Simulation gro\ss er Systeme',
66 67
Universit\"at Stuttgart,\\
Universit\"atsstr.~38, D-70569 Stuttgart, Germany}\\
68 69
%
\bigskip
70
{\normalsize $^\dagger$Abteilung f\"ur Angewandte Mathematik, Universit\"at Freiburg,\\
71 72 73
Hermann-Herder-Str.~10, D-79104 Freiburg, Germany}\\
%
\bigskip
Martin Nolte's avatar
Martin Nolte committed
74 75 76 77
{\normalsize $^\mathparagraph$Institut f\"ur Numerische und Angewandte Mathematik, Universit\"at M\"unster,\\
Einsteinstr.~62, D-48149 M\"unster, Germany}\\
%
\bigskip
78
{\normalsize $^\ddagger$Institut f\"ur Mathematik II,\\ Freie Universit\"at Berlin,
79 80 81
Arnimallee 2-6, D-14195 Berlin, Germany}\\
%
\bigskip
82
{\normalsize \texttt{\url{http://www.dune-project.org/}}}\\
83 84
}

Peter Bastian's avatar
Peter Bastian committed
85 86
\makeindex

Peter Bastian's avatar
Peter Bastian committed
87 88 89 90
\begin{document}

\maketitle

91 92
\begin{abstract}
This document gives an introduction to the Distributed and Unified
93
Numerics Environment (\Dune). \Dune{} is a template library for the
94
numerical solution of partial differential equations. It is based on
Oliver Sander's avatar
Oliver Sander committed
95
the following principles: i) Separation of data structures and
96 97 98 99
algorithms by abstract interfaces, ii) Efficient implementation of these
interfaces using generic programming techniques (templates) in C++ and
iii) Reuse of existing finite element packages with a large body of
functionality. This introduction covers only the abstract grid interface
100 101
of \Dune{} which is currently the most developed part. However, part of
\Dune{} are also the Iterative Solver Template Library (ISTL, providing a
102 103 104
large variety of solvers for sparse linear systems) and a flexible class
hierarchy for finite element methods. These will be described in
subsequent documents. Now have fun!
105 106 107 108

\vspace*{\fill}
Thanks to Martin Drohmann for adapting this howto to version 1.2 of the
DUNE grid interface.
109
\end{abstract}
Peter Bastian's avatar
Peter Bastian committed
110

111
\tableofcontents
Peter Bastian's avatar
Peter Bastian committed
112 113


114 115 116 117 118 119
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

120
\section{What is \texorpdfstring{\Dune{}}{DUNE} anyway?}
121

122
\Dune{} is a software framework for the numerical solution of partial
123 124 125
differential equations with grid-based methods. It is based on the
following main principles:
\begin{itemize}
126
\item \textit{Separation of data structures and
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
algorithms by abstract interfaces.} This provides more functionality
with less code and also ensures maintainability and
extendability of the framework.
\item \textit{Efficient implementation of these
interfaces using generic programming techniques}. Static polymorphism
allows the compiler to do more optimizations, in particular function
inlining, which in turn allows the interface to have very small
functions (implemented by one or few machine instructions) without a
severe performance penalty. In essence the algorithms are parametrized
with a particular data structure and the interface is removed at
compile time. Thus the resulting code is as efficient as if it would
have been written for the special case.
\item \textit{Reuse of existing finite element packages with a large body of
functionality.} In particular the finite element codes UG, \cite{ug},
Alberta, \cite{Alberta}, and ALU3d, \cite{ALU3d}, have been
142
adapted to the \Dune{} framework. Thus, parallel and adaptive meshes with
143 144 145 146
multiple element types and refinement rules are available. All these
packages can be linked together in one executable.
\end{itemize}

147 148
The framework consists of a number of modules which are downloadable
as separate packages.  The current core modules are:
149
\begin{itemize}
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
\item \texttt{dune-common} contains the basic classes used by all
  \Dune{}-modules.  It provides some infrastructural classes for
  debugging and exception handling as well as a library to handle
  dense matrices and vectors.
\item \texttt{dune-grid} is the most mature module and is covered in
  this document. It defines nonconforming, hierarchically nested,
  multi-element-type, parallel grids in arbitrary space dimensions.
  Graphical output with several packages is available, e.~g.~file
  output to IBM data explorer and VTK (parallel XML format for
  unstructured grids). The graphics package Grape, \cite{Grape} has
  been integrated in interactive mode.
\item \texttt{dune-istl} -- \textit{Iterative Solver Template
    Library.} Provides generic sparse matrix/vector classes and a
  variety of solvers based on these classes. A special feature is the
  use of templates to exploit the recursive block structure of finite
  element matrices at compile time. Available solvers include Krylov
  methods, (block-) incomplete decompositions and aggregation-based
  algebraic multigrid.
168 169
\end{itemize}

170
Before starting to work with \Dune{} you might want to update your
171 172 173 174 175 176
knowledge about C++ and templates in particular. For that you should
have the bible, \cite{Stroustrup}, at your desk. A good introduction,
besides its age, is still the book by Barton and Nackman,
\cite{BN}. The definitive guide to template programming is
\cite{VandervoordeJosuttis}. A very useful compilation of template
programming tricks with application to scientific computing is given
Sreejith Pulloor Kuttanikkad's avatar
typo  
Sreejith Pulloor Kuttanikkad committed
177
in \cite{Veldhui99} (if you can't find it on the web, contact us).
178 179 180

\section{Download}

181
The source code of the \Dune{} framework can be
182 183 184 185
downloaded from the web page.  To get started, it is easiest to
download the latest stable version of the tarballs of
\texttt{dune-common}, \texttt{dune-grid} and \texttt{dune-grid-howto}.
These are available on the \Dune{} download page:
186 187
%
\begin{center}
188 189
\href{http://www.dune-project.org/download.html}%
{\texttt{http://www.dune-project.org/download.html}}
190 191
\end{center}
%
Peter Bastian's avatar
Peter Bastian committed
192

193 194
Alternatively, you can download the latest development version via
anonymous SVN.  For further information, please see the web page.
Peter Bastian's avatar
Peter Bastian committed
195

196
\section{Installation}
Peter Bastian's avatar
Peter Bastian committed
197

198
The official installation instructions are available on the web page
Peter Bastian's avatar
Peter Bastian committed
199 200
%
\begin{center}
201 202
\href{http://www.dune-project.org/doc/installation-notes.html}%
{\texttt{http://www.dune-project.org/doc/installation-notes.html}}
Peter Bastian's avatar
Peter Bastian committed
203 204
\end{center}

205
Obviously, we do not want to copy all this information because it might
206
get outdated and inconsistent then. To make this document
207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
self-contained, we describe only how to install \Dune{} from the
tarballs.  If you prefer to use the version from SVN, see the web page
for further information.  Moreover, we assume that you use a UNIX
system. If you have the Redmond system then ask them how to install
it.

In order to build the \Dune{} framework, you need a standards
compliant C++ compiler.  We tested compiling with GNU \texttt{g++} in
version $\geq 3.4.1$ and Intel \texttt{icc}, version 7.0 or 8.0.

Now extract the tarballs of \texttt{dune-common}, \texttt{dune-grid}
and \texttt{dune-grid-howto} into a common directory, say
\texttt{dune-home}.  Change to this directory and call
\begin{lstlisting}
> dune-common-1.0/bin/dunecontrol all
\end{lstlisting}
Replace ``\texttt{1.0}'' by the actual version number of the package
you downloaded if necessary.  This should configure and build all
\Dune{} modules in \texttt{dune-home} with a basic configuration.

For many of the examples in this howto you need adaptive grids or the
parallel features of \Dune{}.  To use adaptive grids, you need to
install one of the external grid packages which \Dune{} provides
interfaces for, for instance Alberta, UG and ALUGrid.
231
\begin{itemize}
232 233 234
\item Alberta -- \href{http://www.alberta-fem.de/}{\texttt{http://www.alberta-fem.de/}}
\item UG -- \href{http://sit.iwr.uni-heidelberg.de/~ug/}{\texttt{http://sit.iwr.uni-heidelberg.de/~ug/}}
\item ALUGrid-- \href{http://www.mathematik.uni-freiburg.de/IAM/Research/alugrid/}{\texttt{http://www.mathematik.uni-freiburg.de/IAM/Research/alugrid/}}
235
\end{itemize}
236 237 238 239 240 241 242 243 244 245 246 247
To use the parallel code of \Dune{}, you need an implementation of the
Message Passing Interface (MPI), for example MPICH or LAM.  For the
\Dune{} build system to find these libraries, the \texttt{configure}
scripts of the particular \Dune{} modules must be passed the locations
of the respective installations.  The \texttt{dunecontrol} script
facilitates to pass options to the \texttt{configure} via a
configuration file.  Such a configuration file might look like this:
\begin{lstlisting}
CONFIGURE_FLAGS="--with-alugrid=/path/to/alugrid/ "\
"--with-alberta=/path/to/alberta "\
"--with-ug=/path/to/ug --enable-parallel"
MAKE_FLAGS="-j 2"
248
\end{lstlisting}
249 250 251 252
If this is saved under the name \texttt{dunecontrol.opts}, you
can tell \texttt{dunecontrol} to cinsider the file by calling
\begin{lstlisting}
> dune-common-1.0/bin/dunecontrol --opts=dunecontrol.opts all
253 254
\end{lstlisting}

255 256
For information on how to build and configure the respective grids,
please see the \Dune{} web page.
257

Peter Bastian's avatar
Peter Bastian committed
258 259
\section{Code documentation}

260
Documentation of the files and classes in \Dune{} is provided in code and
Peter Bastian's avatar
Peter Bastian committed
261 262
can be extracted using the
doxygen\footnote{\href{http://www.stack.nl/~dimitri/doxygen/}{\texttt{http://www.stack.nl/$\sim$dimitri/doxygen/}}}
Peter Bastian's avatar
Peter Bastian committed
263
software available elsewhere. The code documentation can either be built
264
locally on your machine (in html and other formats, e.g.~\LaTeX) 
Peter Bastian's avatar
Peter Bastian committed
265
or its latest version is available at
Peter Bastian's avatar
Peter Bastian committed
266
\begin{center}
267 268
\href{http://www.dune-project.org/doc/}%
{\texttt{http://www.dune-project.org/doc/}}
Peter Bastian's avatar
Peter Bastian committed
269 270
\end{center}

Peter Bastian's avatar
Peter Bastian committed
271
%\section{How to start a new DUNE project}
Peter Bastian's avatar
Peter Bastian committed
272 273 274

\section{Licence}

275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297
The \Dune{} library and headers are licensed under version 2 of the
GNU General Public License%
\footnote{\href{http://www.gnu.org/licenses/gpl.html}%
  {\texttt{http://www.gnu.org/licenses/gpl.html}}}, with a special
exception for linking and compiling against \Dune{}, the so-called
``runtime exception.''  The license is intended to be similiar to the
GNU Lesser General Public License, which by itself isn't suitable for
a C++ template library.

The exact wording of the exception reads as follows:

\begin{quote}  
   As a special exception, you may use the \Dune{} source files as part
   of a software library or application without restriction.
   Specifically, if other files instantiate templates or use macros or
   inline functions from one or more of the \Dune{} source files, or you
   compile one or more of the \Dune{} source files and link them with
   other files to produce an executable, this does not by itself cause
   the resulting executable to be covered by the GNU General Public
   License.  This exception does not however invalidate any other
   reasons why the executable file might be covered by the GNU General
   Public License.
\end{quote}
298

Peter Bastian's avatar
Peter Bastian committed
299
%\section{Contributing to DUNE}
Peter Bastian's avatar
Peter Bastian committed
300 301 302



303 304 305

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Peter Bastian's avatar
Peter Bastian committed
306
\chapter{Getting started}
307 308
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Peter Bastian's avatar
Peter Bastian committed
309 310 311 312 313 314 315

In this section we will take a quick tour through the abstract
grid interface provided by \Dune. This should give you an overview of
the different classes before we go into the details.

\section{Creating your first grid}

Peter Bastian's avatar
Peter Bastian committed
316 317
Let us start with a replacement of the famous ``hello world''
program given below.
Peter Bastian's avatar
Peter Bastian committed
318

Peter Bastian's avatar
Peter Bastian committed
319
\begin{lst}[File dune-grid-howto/gettingstarted.cc] \mbox{}
Peter Bastian's avatar
Peter Bastian committed
320 321 322 323 324
\lstinputlisting[basicstyle=\ttfamily\scriptsize,numbers=left, 
numberstyle=\tiny, numbersep=5pt]{../gettingstarted.cc}
\end{lst}

This program is quite simple. It starts with some includes in lines
325 326 327 328
\ref{gs:inc0}-\ref{gs:inc1}. The file \lstinline!config.h! has been
produced by the \lstinline!configure! script in the application's
build system. It contains the current configuration and can be used to
compile different versions of your code depending on the configuration
329
selected. It is important that this file is included before any other
330 331
\Dune{} header files. The next file \lstinline!dune/grid/sgrid.hh!
includes the headers for the \lstinline!SGrid! class which provides a
332 333
special implementation of the \Dune{} grid interface with a
structured mesh of arbitrary dimension. Then
334 335
\lstinline!dune/grid/common/gridinfo.hh!  loads the headers of some
functions which print useful information about a grid.
Peter Bastian's avatar
Peter Bastian committed
336 337

Since the dimension will be used as a template parameter in many
338 339
places below we define it as a constant in line number \ref{gs:dim}.
The \lstinline!SGrid! class template takes two template parameters
340 341 342 343 344
which are the dimension of the grid and the
dimension of the space where the grid is embedded in (its world
dimension).   If the world dimension is strictly greater than the
grid dimension the surplus coordinates of each grid vertex
are set to zero.  For ease of writing we
345 346
define in line \ref{gs:gridtype} the type \lstinline!GridType! using
the selected value for the dimension. All identifiers of the \Dune{}
Peter Bastian's avatar
Peter Bastian committed
347 348
framework are within the \lstinline!Dune! namespace.

349 350 351 352 353 354 355 356 357
Lines \ref{gs:par0}-\ref{gs:par1} prepare the arguments for the
construction of an \lstinline!SGrid! object. These arguments use the
class template \lstinline!FieldVector<T,n>! which is a vector with
\lstinline!n!  components of type \lstinline!T!. You can either assign
the same value to all components in the constructor (as is done here)
or you could use \lstinline!operator[]! to assign values to individual
components.  The variable \lstinline!N! defines the number of cells or
elements to be used in the respective dimension of the grid.
\lstinline!L! defines the coordinates of the lower left corner of the
358 359
cube and \lstinline!H!  defines the coordinates of the upper right corner of the cube.
Finally in line \ref{gs:grid} we are now able to
360
instantiate the \lstinline!SGrid!  object.
Peter Bastian's avatar
Peter Bastian committed
361 362 363 364 365

The only thing we do with the grid in this little example is printing
some information about it. After successfully running the executable
\lstinline!gettingstarted! you should see an output like this:

Peter Bastian's avatar
Peter Bastian committed
366 367
\begin{lst}[Output of gettingstarted] \mbox{}

Peter Bastian's avatar
Peter Bastian committed
368 369 370 371 372 373
\begin{lstlisting}[basicstyle=\ttfamily\scriptsize]
=> SGrid(dim=3,dimworld=3)
level 0 codim[0]=27 codim[1]=108 codim[2]=144 codim[3]=64
leaf    codim[0]=27 codim[1]=108 codim[2]=144 codim[3]=64
leaf dim=3 geomTypes=((cube,3)[0]=27,(cube,2)[1]=108,(cube,1)[2]=144,(cube,0)[3]=64)
\end{lstlisting}
Peter Bastian's avatar
Peter Bastian committed
374
\end{lst}
Peter Bastian's avatar
Peter Bastian committed
375 376

The first line tells you that you are looking at an \lstinline!SGrid!
377
object of the given dimensions. The \Dune{} grid interface supports
Peter Bastian's avatar
Peter Bastian committed
378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399
unstructured, locally refined, logically nested grids. The coarsest
grid is called level-0-grid or macro grid. Elements can be
individually refined into a number of smaller elements. Each element
of the macro grid and all its descendents obtained from refinement
form a tree structure. All elements at depth $n$ of a refinement tree
form the level-$n$-grid. All elements which are leafs of a refinement
tree together form the so-called leaf grid. The second line of the
output tells us that this grid object consists only of a single level
(level $0$) while the next line tells us that that level 0 coincides
also with the leaf grid in this case. Each line reports about the
number of grid entities which make up the grid. We see that there are
27 elements (codimension 0), 108 faces (codimension 1), 144 edges
(codimension 2) and 64 vertices (codimension 3) in the grid. The last
line reports on the different types of entities making up the grid. In
this case all entities are of type ``cube''.

\begin{exc} Try to play around with different grid sizes by assigning
  different values to the \lstinline!N! parameter. You can also change
  the dimension of the grid by varying \lstinline!dim!. Don't be
  modest. Also try dimensions 4 and 5!
\end{exc}

400 401 402 403 404 405 406 407
\begin{exc} 
  The static methods \lstinline!Dune::gridlevellist! and
  \lstinline!Dune::gridleaflist! produce a very detailed output of the grid's
  elements on a specified grid level. Change the code and print out this
  information for the leaf grid or a grid on lower level. Try to understand the
  output. 
\end{exc}

Peter Bastian's avatar
Peter Bastian committed
408 409 410
\section{Traversing a grid --- A first look at the grid interface}

After looking at very first simple example we are now ready to go on
Peter Bastian's avatar
Peter Bastian committed
411
to a more complicated one. Here it is:
Peter Bastian's avatar
Peter Bastian committed
412

413
\begin{lst}[File dune-grid-howto/traversal.cc] \mbox{}
Peter Bastian's avatar
Peter Bastian committed
414
\nopagebreak
Peter Bastian's avatar
Peter Bastian committed
415 416 417 418
\lstinputlisting[basicstyle=\ttfamily\scriptsize,numbers=left, 
numberstyle=\tiny, numbersep=5pt]{../traversal.cc}
\end{lst}

419
The \lstinline!main! function near the end of the listing is pretty
420
similar to the previous one except that we use a 2d grid for the unit
421 422 423 424 425 426
square that just consists of one cell. In line \ref{tc:refine} this
cell is refined once using the standard method of grid refinement of
the implementation. Here, the cell is refined into four smaller cells.
The main work is done in a call to the function \lstinline!traversal!
in line \ref{tc:call}.  This function is given in lines
\ref{tc:tra0}-\ref{tc:tra1}.
Peter Bastian's avatar
Peter Bastian committed
427 428

The function \lstinline!traversal! is a function template that is
429 430 431 432
parameterized by a class \lstinline!G! that is assumed to implement
the \Dune{} grid interface.  Thus, it will work on \textit{any} grid
available in \Dune{} without any changes. We now go into the details
of this function.
Peter Bastian's avatar
Peter Bastian committed
433 434

The algorithm should work in any dimension so we extract the grid's
435 436 437
dimension in line \ref{tc:dim}. Next, each \Dune{} grid defines a type
that it uses to represent positions. This type is extracted in line
\ref{tc:ct} for later use.
Peter Bastian's avatar
Peter Bastian committed
438 439 440 441

A grid is considered to be a container of ``entities'' which are
abstractions for geometric objects like vertices, edges,
quadrilaterals, tetrahedra, and so on. This is very similar to the
Peter Bastian's avatar
Peter Bastian committed
442 443 444
standard template library (STL), see e.~g.~\cite{Stroustrup},
which is part of any C++ system. 
A key difference is, however, that there is not just one type of entity but
Peter Bastian's avatar
Peter Bastian committed
445
several. As in the STL the elements of any container can be accessed
446
with iterators which are generalized pointers. Again, a \Dune{} grid
Peter Bastian's avatar
Peter Bastian committed
447 448
knows several different iterators which provide access to the
different kinds of entities and which also provide different patterns
449 450 451 452 453 454
of access.

As we usually do not want to use the entire hierarchy of the grid, we first
define a view on that part of the grid we are interested in. This can be a
level or the leaf part of the grid. In line \ref{tc:lfgv} a type for a
\lstinline!GridView! on the leaf grid is defined.
Peter Bastian's avatar
Peter Bastian committed
455

456
Line \ref{tc:ittype} extracts the type of an iterator from this view 
Peter Bastian's avatar
Peter Bastian committed
457 458 459
class. \lstinline!Codim! is a \lstinline!struct! within the grid class
that takes an integer template parameter specifying the codimension
over which to iterate. Within the \lstinline!Codim! structure the type
460
\lstinline!Iterator! is defined. Since we specified codimension 0
Peter Bastian's avatar
Peter Bastian committed
461
this iterator is used to iterate
462
over the elements which are not refined any further, i.e.~which are
Peter Bastian's avatar
Peter Bastian committed
463 464
the leaves of the refinement trees.

465
The \lstinline!for!-loop in line \ref{tc:forel} now visits every such
466 467 468 469 470
element. The \lstinline!begin! and \lstinline!end! on the
\lstinline!LeafGridView!
class deliver the first leaf element and one past the last leaf element. Note
that the \lstinline!template! keyword must be used and template parameters are
passed explicitely. Within the loop body in
471 472 473 474 475 476 477 478 479 480 481 482 483 484 485
lines \ref{tc:forel0}-\ref{tc:forel1} the iterator \lstinline!it! acts
like a pointer to an entity of dimension \lstinline!dim! and
codimension 0. The exact type would be
\lstinline!typename G::template Codim<0>::Entity! just to mention it.

An important part of an entity is its geometrical shape and position.
All geometrical information is factored out into a sub-object that can
be accessed via the \lstinline!geometry()!  method. The geometry
object is in general a mapping from a $d$-dimensional polyhedral
reference element to $w$ dimensional space. Here we have $d=$
\lstinline!G::dimension! and $w=$ \lstinline!G::dimensionworld!. This
mapping is also called the ``local to global'' mapping.  The
corresponding reference element has a certain type which is extracted
in line \ref{tc:reftype}. Since the reference elements are polyhedra
they consist of a finite number of corners. The images of the corners
486 487
under the local to global map can be accessed via the
\lstinline!corner(int n)! method. Line \ref{tc:print} prints the geometry type
488 489
and the position of the first corner of the element. Then line
\ref{tc:count} just counts the number of elements visited.
Peter Bastian's avatar
Peter Bastian committed
490 491 492 493 494

Suppose now that we wanted to iterate over the vertices of the leaf
grid instead of the elements. Now vertices have the codimension
\lstinline!dim! in a \lstinline!dim!-dimensional grid and a
corresponding iterator is provided by each grid class. It is extracted
495 496 497 498 499
in line \ref{tc:vertit} for later use. The \lstinline!for!-loop
starting in line \ref{tc:forve} is very similar to the first one
except that it now uses the \lstinline!VertexLeafIterator!.  As you
can see the different entities can be accessed with the same methods.
We will see later that codimensions 0 and \lstinline!dim! are
Peter Bastian's avatar
Peter Bastian committed
500 501 502 503 504 505 506
specializations with an extended interface compared to all other
codimensions. You can also access the codimensions between 0 and
\lstinline!dim!. However, currently not all implementations of the
grid interface support these intermediate codimensions (though this
does not restrict the implementation of finite element methods with
degrees of freedom associated to, say, faces).

507 508
Finally, we show in lines \ref{tc:level0}-\ref{tc:level1} how the
hierarchic structure of the mesh can be accessed. To that end a
509 510 511
\lstinline!LevelGridView! is used. It provides via an \lstinline!Iterator!
access to all entities of a given codimension (here 0) on a given grid level.
The coarsest
512 513
grid level (the initial macro grid) has number zero and the number of
the finest grid level is returned by the \lstinline!maxLevel()! method
514 515
of the grid.  The methods \lstinline!begin()! and \lstinline!end()!
on the view deliver iterators to the first and one-past-the-last
516 517
entity of a given grid level supplied as an integer argument to these
methods.
Peter Bastian's avatar
Peter Bastian committed
518 519 520 521

The following listing shows the output of the program.

\begin{lst}[Output of traversal] \mbox{}
Peter Bastian's avatar
Peter Bastian committed
522 523

\begin{lstlisting}[basicstyle=\ttfamily\scriptsize]
Peter Bastian's avatar
Peter Bastian committed
524
*** Traverse codim 0 leaves
Peter Bastian's avatar
Peter Bastian committed
525 526 527 528 529 530
visiting leaf (cube, 2) with first vertex at -1 -1
visiting leaf (cube, 2) with first vertex at 0 -1
visiting leaf (cube, 2) with first vertex at -1 0
visiting leaf (cube, 2) with first vertex at 0 0
there are/is 4 leaf element(s)

Peter Bastian's avatar
Peter Bastian committed
531
*** Traverse codim 2 leaves
Peter Bastian's avatar
Peter Bastian committed
532 533 534 535 536 537 538 539 540
visiting (cube, 0) at -1 -1
visiting (cube, 0) at 0 -1
visiting (cube, 0) at 1 -1
visiting (cube, 0) at -1 0
visiting (cube, 0) at 0 0
visiting (cube, 0) at 1 0
visiting (cube, 0) at -1 1
visiting (cube, 0) at 0 1
visiting (cube, 0) at 1 1
Peter Bastian's avatar
Peter Bastian committed
541 542 543 544 545 546 547 548 549 550 551
there are/is 9 leaf vertices(s)

*** Traverse codim 0 level-wise
visiting (cube, 2) with first vertex at -1 -1
there are/is 1 element(s) on level 0

visiting (cube, 2) with first vertex at -1 -1
visiting (cube, 2) with first vertex at 0 -1
visiting (cube, 2) with first vertex at -1 0
visiting (cube, 2) with first vertex at 0 0
there are/is 4 element(s) on level 1
Peter Bastian's avatar
Peter Bastian committed
552
\end{lstlisting}
Peter Bastian's avatar
Peter Bastian committed
553
\end{lst}
Peter Bastian's avatar
Peter Bastian committed
554 555 556 557

\begin{rem} Define the end iterator for efficiency. 
\end{rem}

Peter Bastian's avatar
Peter Bastian committed
558 559 560 561 562 563 564 565 566
\begin{exc} Play with different dimensions, codimension
  (\lstinline!SGrid! supports all codimenions) and refinements.
\end{exc}

\begin{exc} The method \lstinline!corners()! of the geometry returns
  the number of corners of an entity. Modify the code such that the
  positions of all corners are printed.
\end{exc}

567 568 569

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
570
\chapter{The \texorpdfstring{\Dune{}}{DUNE} grid interface}
571 572
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Peter Bastian's avatar
Peter Bastian committed
573 574


575
\section{Grid definition}
Peter Bastian's avatar
Peter Bastian committed
576

577 578 579 580 581
There is a great variety of grids: conforming and non-conforming
grids, single-element-type and multiple-element-type grids, locally
and globally refined grids, nested and non-nested grids,
bisection-type grids, red-green-type grids, sparse grids and so on. In
this section we describe in some detail the type of grids that are
582
covered by the \Dune{} grid interface.
Peter Bastian's avatar
Peter Bastian committed
583

584
\minisec{Reference elements}
Peter Bastian's avatar
Peter Bastian committed
585 586 587 588 589 590

A computational grid is a nonoverlapping subdivision of a domain
$\Omega\subset\R^w$ into elements of ``simple'' shape. Here ``simple''
means that the element can be represented as the image of a reference
element\index{reference element} under a transformation. A reference element is a convex
polytope, which is a bounded intersection of a finite set of
591 592 593 594 595
half-spaces. 

\minisec{Dimension and world dimension}

A grid has a dimension $d$ which is the dimensionality of
Peter Bastian's avatar
Peter Bastian committed
596 597 598
its reference elements. Clearly we have $d\leq w$. In the case $d<w$ the grid
discretizes a $d$-dimensional manifold. 

599 600 601 602
\minisec{Faces, entities and codimension}

The intersection of a $d$-dimensional convex polytope (in
$d$-dimensional space) with a
Peter Bastian's avatar
Peter Bastian committed
603 604 605 606 607 608 609 610 611
tangent plane is called a face (note that there are faces of
dimensionality $0,\ldots,d-1$). Consequently, a face of a grid element
is defined as the image of a face of its reference element under the
transformation. The elements and faces of elements of a grid are
called its entities. An entity is said to be of codimension $c$ if it
is a $d-c$-dimensional object. Thus the elements of the grid are
entities of codimension 0, facets of an element have codimension 1,
edges have codimension $d-1$ and vertices have codimension $d$.

612 613
\minisec{Conformity}

Peter Bastian's avatar
Peter Bastian committed
614 615 616 617
Computational grids come in a variety of flavours: A
{conforming} grid is one where the intersection of two
elements is either empty or a face of each of the two elements. 
Grids where the intersection of two elements may have an
618 619 620 621 622
arbitrary shape are called {nonconforming}. 

\minisec{Element types}

A {simplicial} grid is one where the reference elements are
Peter Bastian's avatar
Peter Bastian committed
623
simplices. In a {multi-element-type} grid a finite number of
624
different reference elements are allowed. The \Dune{} grid interface
Peter Bastian's avatar
Peter Bastian committed
625 626
can represent conforming as well as non-conforming grids.

627 628
\minisec{Hierarchically nested grids, macro grid}

Peter Bastian's avatar
Peter Bastian committed
629 630 631 632 633 634 635 636 637 638 639 640 641 642
A {hierarchically nested} grid consists of a collection of $J+1$
grids that are subdivisions of nested domains $$\Omega=\Omega_0 \supseteq \Omega_1 \supseteq
\ldots \supseteq \Omega_J.$$ Note that only $\Omega_0$ is required to
be identical to $\Omega$. If $\Omega_0=\Omega_1=\ldots=\Omega_J$ the
grid is {globally refined}, otherwise it is {locally refined}.
The grid that discretizes $\Omega_0$ is called the macro grid and its
elements the macro elements. The
grid for $\Omega_{l+1}$ is obtained from the grid
for $\Omega_l$ by possibly subdividing each of its elements into
smaller elements. Thus, each element of the macro grid and the
elements that are obtained from refining it form a tree structure. The
grid discretizing $\Omega_l$ with $0\leq l \leq J$ is called the level-$l$-grid and its
elements are obtained from an $l$-fold refinement of some macro elements.

643 644 645 646
\minisec{Leaf grid}

Due to the nestedness of the domains we can partition the domain
$\Omega$ into $$\Omega = \Omega_J \cup \bigcup_{l=0}^{J-1}
Peter Bastian's avatar
Peter Bastian committed
647 648 649 650 651 652 653 654 655 656 657
\Omega_l\setminus\Omega_{l+1}.$$ As a consequence of the hierarchical
construction a computational grid discretizing $\Omega$ can be
obtained by taking the elements of the level-$J$-grid plus
the elements of the level-$J-1$-grid in the region
$\Omega_{J-1}\setminus\Omega_{J}$ plus the elements of the level-$J-2$-grid in the region
$\Omega_{J-2}\setminus\Omega_{J-1}$ and so on plus the elements of the level-$0$-grid in the region
$\Omega_{0}\setminus\Omega_{1}$. The grid resulting from this
procedure is called the leaf grid
because it is formed by the leaf elements of the trees emanating at
the macro elements. 

658 659
\minisec{Refinement rules}

Peter Bastian's avatar
Peter Bastian committed
660 661 662 663 664
There is a variety of ways how to hierarchically refine a grid. The
refinement is called conforming if the leaf grid is always a
conforming grid, otherwise the refinement is called
non-conforming. Note that the grid on each level $l$ might be
conforming while the leaf grid is not. 
665 666 667 668
There are also many ways how to subdivide an individual element into
smaller elements. Bisection always subdivides elements into two
smaller elements, thus the resulting data structure is a binary tree
(independent of the dimension of the grid). Bisection is sometimes
669
called ``green'' refinement. The so-called ``red'' refinement is the
670 671 672 673 674 675
subdivision of an element into $2^d$ smaller elements, which is most
obvious for cube elements. In many practical situation anisotropic
refinement, i.~e.~refinement in a preferred direction, may be required.

\minisec{Summary}

676
The \Dune{} grid interface is able to represent grids with the
677 678 679 680 681 682 683 684 685 686 687 688 689 690 691
following properties:
\begin{itemize}
\item Arbitrary dimension.
\item Entities of all codimensions.
\item Any kind of reference elements (you could define the icosahedron
  as a reference element if you wish).
\item Conforming and non-conforming grids.
\item Grids are always hierarchically nested.
\item Any type of refinement rules.
\item Conforming and non-conforming refinement.
\item Parallel, distributed grids.
\end{itemize}



Peter Bastian's avatar
Peter Bastian committed
692 693 694 695 696 697 698 699 700 701 702 703
\section{Concepts}

Generic algorithms are based on concepts. A concept is a kind of
``generalized'' class with a well defined set of members. 
Imagine a function template that takes a type \lstinline!T!
as template argument. All the members of \lstinline!T!, i.e.
methods, enumerations, data (rarely) and nested
classes  used by the function template form the concept. From that
definition it is clear that the concept does not necessarily exist as
program text. 

A class that implements a concept is called a
704
\textit{model} of the concept. E.g.~in the standard template library (STL)
Peter Bastian's avatar
Peter Bastian committed
705 706 707 708 709 710 711 712 713 714
the class \lstinline!std::vector<int>! is a model of the concept
``container''. If all instances of a class template are a model of
a given concept we can also say that the class template is a model of
the concept. In that sense \lstinline!std::vector! is also a model of
container.  

In standard OO language a concept would be formulated as
an abstract base class and all the models would be implemented as
derived classes. However, for reasons of efficiency we do not want to
use dynamic polymorphism. Moreover, concepts are more powerful because
715
the models of a concept can use different types, e.g.~as return types of
Peter Bastian's avatar
Peter Bastian committed
716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752
methods. As an example consider the STL where the begin method on a
vector of int returns \lstinline!std::vector<int>::iterator! and on a
list of int it returns \lstinline!std::list<int>::iterator! which may
be completely different types. 

Concepts are difficult to describe when they do not exist as concrete
entities (classes or class templates) in a program. The STL way of
specifying concepts is to describe the members \lstinline!X::foo()! of
some arbitrary model named \lstinline!X!. Since this decription of the
concept is not processed by the compiler it can get inconsistent and
there is no way to check conformity of a model to the interface. As a
consequence, strange error messages from the compiler may be the
result (well C++ compilers can always produce strange error messages).
There are two ways to improve the situation:
\begin{itemize}
\item \textit{Engines:} A class template is defined that wraps the
  model (which is the template parameter) and forwards all member
  function calls to it. In addition all the nested types and
  enumerations of the model are copied into the wrapper class. 
  The model can be seen as an engine that powers the wrapper class,
  hence the name. Generic
  algorithms are written in terms of the wrapper class. Thus the
  wrapper class encapsulates the concept and it can be ensured
  formally by the compiler that
  all members of the concept are implemented.

\item \textit{Barton-Nackman trick:} This is a refinement of the
  engine approach where the models are derived from the wrapper class
  template in addition. Thus static polymorphism is combined
  with a traditional class hierarchy, see \cite{Veldhui99,BN}. 
  However, the
  Barton-Nackman trick gets rather involved when the derived classes
  depend on additional template parameters and several types are related
  with each other. That is why it is not used at all places in \Dune.
\end{itemize}


753
The \Dune{} grid interface now consists of a \textit{set of related concepts}.
Peter Bastian's avatar
Peter Bastian committed
754 755 756 757 758
Either the engine or the Barton-Nackman approach are used to clearly
define the concepts. In order to avoid any inconsistencies we refer as
much as possible to the doxygen-generated documentation. For an
overview of the grid interface see the web page 
\begin{center}
759 760
\href{http://www.dune-project.org/doc/doxygen/html/group__Grid.html}%
{\texttt{http://www.dune-project.org/doc/doxygen/html/group\_\_Grid.html}}.
Peter Bastian's avatar
Peter Bastian committed
761 762 763 764 765
\end{center}



\subsection{Common types}
Peter Bastian's avatar
Peter Bastian committed
766

Peter Bastian's avatar
Peter Bastian committed
767 768
Some types in the grid interface do not depend on a specific model,
i.~e.~they are shared by all implementations.
Peter Bastian's avatar
Peter Bastian committed
769

770
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1ReferenceElement.html}{Dune::ReferenceElement}}
Peter Bastian's avatar
Peter Bastian committed
771

Peter Bastian's avatar
Peter Bastian committed
772 773 774
describes the topology and geometry of standard entities. Any given
entity of the grid can be completely specified by a reference element
and a map from this reference element to world coordinate space. 
Peter Bastian's avatar
Peter Bastian committed
775

776
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1GeometryType.html}{Dune::GeometryType}}
Peter Bastian's avatar
Peter Bastian committed
777

Peter Bastian's avatar
Peter Bastian committed
778
defines names for the reference elements.
Peter Bastian's avatar
Peter Bastian committed
779

780
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1CollectiveCommunication.html}{Dune::CollectiveCommunication}}
Peter Bastian's avatar
Peter Bastian committed
781

Peter Bastian's avatar
Peter Bastian committed
782 783
defines an interface to global communication operations in a portable
and transparent way. In particular also for sequential grids. 
Peter Bastian's avatar
Peter Bastian committed
784 785


786
\subsection{Concepts of the \texorpdfstring{\Dune{}}{DUNE} grid interface}
Peter Bastian's avatar
Peter Bastian committed
787

788
In the following a short description of each concept in the \Dune{}
Peter Bastian's avatar
Peter Bastian committed
789
grid interface is given. For the details click on the link that leads
790
you to the documentation of the corresponding wrapper class template 
Peter Bastian's avatar
Peter Bastian committed
791
(in the engine sense).
Peter Bastian's avatar
Peter Bastian committed
792

793
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1Grid.html}{Grid}}
Peter Bastian's avatar
Peter Bastian committed
794

Peter Bastian's avatar
Peter Bastian committed
795 796 797 798
    The grid 
    is a container of entities that allows to access these entities
    and that knows the number of its entities. You create instances of
    a grid class in your applications, while objects of the other
799
    classes are typically aggregated in the grid class and accessed via
Peter Bastian's avatar
Peter Bastian committed
800
    iterators. 
Peter Bastian's avatar
Peter Bastian committed
801

802 803 804 805 806 807 808 809
\minisec{\href{TODO}{GridView}}

    The GridView gives a view on a level or the leaf part of a grid. It
    provides iterators for access to the elements of this view and a
    communication method for parallel computations. Alternatively, a
    LevelIterator of a LeafIterator  can be directly accessed from a grid.
    These iterator types are described below.

810
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1Entity.html}{Entity}}
Peter Bastian's avatar
Peter Bastian committed
811

Peter Bastian's avatar
Peter Bastian committed
812 813 814 815 816
    The entity class encapsulates
    the topological part of an entity, i.e. its hierarchical
    construction from subentities and the relation to other
    entities. Entities cannot be created, copied or modified by the
    user. They can only be read-accessed through immutable iterators. 
Peter Bastian's avatar
Peter Bastian committed
817

818
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1Geometry.html}{Geometry}}
Peter Bastian's avatar
Peter Bastian committed
819

Peter Bastian's avatar
Peter Bastian committed
820 821 822
    Geometry
    encapsulates the geometric part of an entity by mapping local
    coordinates in a reference element to world coordinates. 
Peter Bastian's avatar
Peter Bastian committed
823

824
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1EntityPointer.html}{EntityPointer}}
Peter Bastian's avatar
Peter Bastian committed
825

Peter Bastian's avatar
Peter Bastian committed
826 827 828 829
    EntityPointer  is a
    dereferenceable type that delivers a reference to an
    entity. Moreover it is immutable, i.e. the referenced entity can
    not be modified. 
Peter Bastian's avatar
Peter Bastian committed
830

831
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1Iterator.html}{Iterator}}
Peter Bastian's avatar
Peter Bastian committed
832

833
    Iterator is an
Peter Bastian's avatar
Peter Bastian committed
834 835
    immutable iterator that provides access to an entity. It can by
    incremented to visit all entities of a given
836 837
    codimension of a GridView. An EntityPointer is assignable
    from an Iterator. 
Peter Bastian's avatar
Peter Bastian committed
838

839
\minisec{\href{http://www.dune-project.org/doc/doxygen/dune-grid-html/group__GIIntersectionIterator.html}{IntersectionIterator}}
Peter Bastian's avatar
Peter Bastian committed
840

841
    IntersectionIterator provides access to all entities of
Peter Bastian's avatar
Peter Bastian committed
842 843 844
    codimension 0 that have an intersection of codimension 1 with a
    given entity of codimension 0. In a conforming mesh these are the
    face neighbors of an element. For two entities with a common
845 846 847 848 849
    intersection the IntersectionIterator can be dereferenced as an Intersection
    object which in turn provides information about the geometric location of
    the intersection.  Furthermore this Intersection class also provides
    information about intersections of an entity
    with
Peter Bastian's avatar
Peter Bastian committed
850
    the internal or external boundaries. 
851 852
    The IntersectionIterator provides intersections between
    codimension 0 entities among the same GridView.
853
    
854
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1IndexSet.html}{LevelIndexSet}, \href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1IndexSet.html}{LeafIndexSet}}
855

Peter Bastian's avatar
Peter Bastian committed
856 857 858
    LevelIndexSet and LeafIndexSet which are both models of
    Dune::IndexSet are used to attach any kind of user-defined data to
    (subsets of) entities of the grid. This data is supposed to be
859 860 861
    stored in one-dimensional arrays for reasons of efficiency. An IndexSet is
    usually not used directly but through a Mapper (c.f.~chapter
    \ref{ch:mappers}).
Peter Bastian's avatar
Peter Bastian committed
862

863
\minisec{\href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1IdSet.html}{LocalIdSet}, \href{http://www.dune-project.org/doc/doxygen/html/classDune_1_1IdSet.html}{GlobalIdSet}}
Peter Bastian's avatar
Peter Bastian committed
864 865 866

    LocalIdSet and GlobalIdSet which are both models of Dune::IdSet
    are used to save user data during a grid refinement phase and
867 868 869 870 871
    during dynamic load balancing in the parallel case. The LocalIdSet is
    unique for all entities on the current partition, whereas the GlobalIdSet
    gives a unique mapping over all grid partitions. An IdSet is usually not used
    directly but through a Mapper (c.f.~chapter
    \ref{ch:mappers}).
Peter Bastian's avatar
Peter Bastian committed
872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888


\section{Propagation of type information}

The types making up one grid implementation cannot be mixed with the
types making up another grid implementation. Say, we have two
implementations of the grid interface \lstinline!XGrid! and
\lstinline!YGrid!. Each implementation provides a LevelIterator
class, named \lstinline!XLevelIterator! and
\lstinline!YLevelIterator! (in fact, these are class templates because
they are parametrized by the codimension and other
parameters). Although these types implement the same interface they
are distinct classes that are not related in any way for the
compiler. As in the Standard Template Library strange error messages
may occur if you try to mix these types.

In order to avoid these problems the related types of an
889 890
implementation are provided as public types by most classes of an
implementation. E.g., in order to extract the
Peter Bastian's avatar
Peter Bastian committed
891 892 893 894 895 896 897 898 899 900 901
\lstinline!XLevelIterator! (for codimension 0) from the
\lstinline!XGrid! class you would write
\begin{lstlisting}
XGrid::template Codim<0>::LevelIterator
\end{lstlisting}
Because most of the types are parametrized by certain parameters like
dimension, codimension or partition type simple typedefs (as in the
STL) are not sufficient here. The types are rather placed in a
struct template, named \lstinline!Codim! here, where the template
parameters of the struct are those of the type. This concept may even
be applied recursively. 
Peter Bastian's avatar
Peter Bastian committed
902

903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981
\chapter{Constructing Grid Objects}

So far we have talked about the grid interface and how you can access and
manipulate grids.  This chapter will show you how you create grids in the
first place.  There are several ways to do this.

The central idea of \Dune is that all grid implementations behave equally
and conform to the same interface.  However, this concept fails when it
comes to constructing grid objects, because grid implementations differ too
much to make one construction method work for all.  For example, for an
unstructured grid you have to specify all vertex positions, whereas for a
structured grid this would be a waste of time.  On the other hand, for
a structured grid you may need to give the bounding box which, for an
unstructured grid, is not necessary.  In practice, these differences do
not pose serious problems.

In this chapter, creating a grid always means creating a grid with only
a single level.  Such grid is alternatively called a {\em coarse grid}
or a {\em macro grid}.  There is currently no functionality in \Dune to
set up hierarchical grids directly.  The underlying assumption is that
the user will create a coarse grid first and then generate a hierarchy
using refinement.  Despite the name (and grid implementations permitting),
the coarse grid can of course be as large and fine as desired.

\section{Creating Structured Grids}

Creating structured grids is comparatively simple, as little information
needs to be provided.  In general, for uniform structured grids, the grid
dimension, bounding box, and number of elements in each direction suffices.
Such information can be given directly with the constructor of the grid
object. \Dune does not currently specify the signature of grid constructors,
and hence they are all slightly different.  For example, to create a 2D
\lstinline!SGrid! in $[0,1]^2 \subset \mathbb{R}^2$ with 10 elements in
each direction call
\begin{lstlisting}
    Dune::FieldVector<int,2> n;
    n[0] = n[1] = 10;

    Dune::FieldVector<double,2> lower;
    lower[0] = lower[1] = 1.0;

    Dune::FieldVector<double,2> upper;
    upper[0] = upper[1] = 1.0;

    Dune::SGrid<2,2> grid(n, lower, upper);
\end{lstlisting}
If you want to do the same for a sequential \lstinline!YaspGrid! the code is
\begin{lstlisting}
    Dune::FieldVector<int,2> n;
    n[0] = n[1] = 10;

    Dune::FieldVector<double,2> upper;
    upper[0] = upper[1] = 1.0;

    Dune::FieldVector<bool,dim> periodic(false);
    
    YaspGrid<2> grid(upper, n, periodic, 0);
\end{lstlisting}
Note that you do not have to specify the lower left corner as \lstinline!YaspGrid!
hardwires it to zero.  The unstructured one-dimensional \lstinline!OneDGrid!
also has a constructor
\begin{lstlisting}
    OneDGrid grid(10,    // number of elements 
                  0.0,   // left domain boundary
                  1.0    // right domain boundary
                  );
\end{lstlisting}
for uniform grids.

\section{Reading Unstructured Grids from Files}

Unstructured grids usually require much more information than what can
reasonable be provided within the program code.  Instead, they are usually
read from special files.  A large variety of different file formats for
finite element grids exists, and \Dune provides support for some of them
Again, no interface specification exists for file readers in \Dune.

Arguably the most important file format currently supported by \Dune is
the \lstinline!gmsh! format.  \lstinline!Gmsh!\footnote{\url{http://geuz.org/gmsh/}}
Peter Bastian's avatar
Peter Bastian committed
982 983 984 985 986
is an open-source grid generator and modeller.  It allows to define
geometries using a boundary representation (interactively and via its
own modelling language resulting in \lstinline!.geo!-files), 
creates simplicial grids in 2d and 3d (using
\lstinline!tetgen! or \lstinline!netgen!)
987
and stores them in files ending in \lstinline!.msh!. \lstinline!Gmsh!
Peter Bastian's avatar
Peter Bastian committed
988
can also be compiled with \lstinline!OpenCascade!, an open-source CAD
989 990 991 992 993
kernel. Via \lstinline!gmsh!
CAD geometries, e.~g.~from IGES or STEP files, can be meshed and subsequently be used in
\Dune. Moreover, the reader supports second order
boundary segments thus providing a rudimentary support for curved boundaries.
To read such a file into a FooGrid, include \lstinline!dune/grid/io/file/gmshreader.hh!
994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202
and write
\begin{lstlisting}
    FooGrid* grid = GmshReader<GridType>::read(filename);
\end{lstlisting}

A second format is AmiraMesh, which is the native format of the Amira
visualization toolbox.\footnote{\url{http://www.amiravis.de/}}
To read AmiraMesh files you need to have the library libamiramesh%
\footnote{http://www.amiravis.com/Ext411-01-libamiramesh/index.html}
installed.  Then
\begin{lstlisting}
    FooGrid* grid = AmiraMeshReader<GridType>::read(filename);
\end{lstlisting}
reads the grid in \lstinline!filename! into the FooGrid.

Further available formats are StarCD and the native Alberta format.
See the class documentation of dune-grid for an up-to-date list.
Demo grids for each format can be found in \lstinline!dune-grid/doc/grids!.



\section{The \texorpdfstring{\Dune}{Dune} Grid Format (DGF)}

Dune has its own macro grid format, the \underline{D}une \underline{G}rid \underline{F}ormat. 
A detailed description of the DGF and how to use it can be found on the
homepage of \Dune% 
\footnote{\url{http://www.dune-project.org/doc/doxygen/dune-grid-html/group__DuneGridFormatParser.html}}.

Here we only give a short introduction. The configuration
\lstinline!--with-grid-dim={1,2,3}! must be provided during configuration run
in order to use the DGF parser. A default grid type can be chosen with the
configuration option  \lstinline!--with-grid-type=ALBERTAGRID!.
Further possible grid types are \lstinline!ALUGRID_CUBE,ALUGRID_SIMPLEX,ALUGRID_CONFORM!, 
\lstinline!ONEDGRID,SGRID,UGGRID!, and \lstinline!YASPGRID!.
Note that both values will also be changeable later. 
If the \lstinline!--with-grid-dim! option was not provided during configuration the 
DFG grid type definition will not work. Nevertheless, the grid parser will work 
but the grid type has to be defined by the user and the appropriate DGF parser 
specialization has to be included. 
Assuming the \lstinline!--with-grid-dim!\ was provided the DGF grid type 
definition works by first including \lstinline!gridtype.hh!.
\begin{lstlisting}[basicstyle=\ttfamily\scriptsize]
#include <dune/grid/io/file/dgfparser/dgfgridtype.hh>
\end{lstlisting}
Depending on the pre-configured values of \lstinline!GRIDDIM!\ and
\lstinline!GRIDTYPE! a typedef for the grid to use will be provided by
including \lstinline!dgfgridtype.hh!. The following example shows how an 
instance of the defined grid is generated. Given a DGF file, for example 
\lstinline!unitcube2.dgf!, a grid pointer is created as follows.
\begin{lstlisting}[basicstyle=\ttfamily\scriptsize]
GridPtr<GridType> gridPtr( "unitcube2.dgf" );
\end{lstlisting}
The grid is accessed be dereferencing the grid pointer.
\begin{lstlisting}[basicstyle=\ttfamily\scriptsize]
GridType& grid = *gridPtr; 
\end{lstlisting}
To change the grid one simply has to re-compile the code using the following make command.
\begin{lstlisting}[basicstyle=\ttfamily\scriptsize]
make GRIDDIM=2 GRIDTYPE=ALBERTAGRID integration 
\end{lstlisting}
This will compile the application \texttt{integration} with grid type \lstinline!ALBERTAGRID! and grid dimension $2$.
Note that before the re-compilation works, 
the corresponding object file has to be removed.

\section{The Grid Factory}
\label{sec:grid_factory}

While there is currently no convention on how a file reader should look like,
there is a formally specified low-level interface for the construction of
unstructured coarse grids.  This interface, which goes by the name of
GridFactory, provides methods to, e.g., insert vertices and elements one by one.
It is the basis of the file readers described in the previous section.
The main reason why you may want to program the GridFactory directly is
when writing your own grid readers.  However, in some cases it may also be
most convenient to be able to specify your coarse grid entirely in the
C++ code.  You can do that using the GridFactory.

The GridFactory is programmed as a factory class (hence the name).
You default construct an object of the factory class, provide it with all
necessary information, and it will create and hand over a grid for you.
In the following we will describe the use of the GridFactory in more detail.
Say you are interested in creating a new grid of type \lstinline!FooGrid!.  Then
you proceed as follows:

\begin{enumerate}
\item Create a GridFactory Object

Get a new GridFactory object by calling

\begin{lstlisting}[basicstyle=\small]
    GridFactory< FooGrid > factory;
\end{lstlisting}

\item Enter the Vertices

Insert the grid vertices by calling

\begin{lstlisting}[basicstyle=\small]
    factory.insertVertex(const FieldVector<ctype,dimworld>& position);
\end{lstlisting}

for each vertex. The order of insertion determines the level- and leaf indices of your level 0 vertices.

\item Enter the elements

For each element call

\begin{lstlisting}[basicstyle=\small]
    factory.insertElement(Dune::GeometryType type, const std::vector<int>& vertices);
\end{lstlisting}

The parameters are

\begin{itemize}
    \item type - The element type. The grid implementation is expected to throw
	an exception if an element type that cannot be handled is encountered.
    \item vertices - The indices of the vertices of this element.
\end{itemize}

The numbering of the vertices of each element is expected to follow the \Dune
conventions. Refer to the page on reference elements for the details.

\item Parametrized Domains

\lstinline!FooGrid! may support parametrized domains. That means that you can provide a smooth description of your grid boundary. The actual grid may always be piecewise linear; however, as you refine, the grid will approach your prescribed boundary. You don't have to do this. If you do not specify the boundary geometry it is left to the grid implementation.

In order to create curved boundary segments, for each segment you have to write a class which implements the correct geometry. These classes are then handed over to the 
factory. Boundary segment implementations must be derived from

\begin{lstlisting}[basicstyle=\small]
    template <int dim, int dimworld> Dune::BoundarySegment
\end{lstlisting}

This is an abstract base class which requires you to overload the method

\begin{lstlisting}[basicstyle=\small]
    virtual FieldVector< double, dimworld > 
         operator() (const FieldVector< double, dim-1 > &local)
\end{lstlisting}

This methods must compute the world coordinates from the local ones on the boundary segment. Give these classes to your grid by calling

\begin{lstlisting}[basicstyle=\small]
    grid.insertBoundarySegment(const std::vector<int>& vertices, 
                               const BoundarySegment<dim,dimworld> *
                                     boundarySegment = NULL);
\end{lstlisting}

Control over the allocated objects is taken from you, and the grid object will take care of their destruction.

Note that you can call \lstinline!insertBoundarySegment! with only the first argument.
In that case, the boundary geometry is left to the grid implementation.  However,
the boundary segments get ordered in the way you inserted them.  This may be
helpful if you have data attached to your coarse grid boundary 
(see Sec.~\ref{sec:import_data_for_new_grids}).

\item Finish construction

To finish off the construction of the FooGrid object call

\begin{lstlisting}[basicstyle=\small]
    FooGrid* grid = factory.createGrid();
\end{lstlisting}

This time it is you who gets full responsibility for the allocated object.
\end{enumerate}

\section{Attaching Data to a New Grid}
\label{sec:import_data_for_new_grids}

In many cases there is data attached to new grids.  This data may be initial
values, spatially distributed material parameters, boundary conditions, etc.
It is associated to elements or vertices, or the boundary segments of the
coarse grid.  The data may be available in a separate data file or even
included in the same file with the grid. 

 The connection with the grid in
the grid file is usually make implicitly.  For example, vertex data is ordered
in the same order as the vertices itself.  Hence the grid-reading process must 
guarantee that vertices and elements are not reordered during grid creation.
More specifically, \Dune guarantees the following: {\em the level and leaf
indices of zero-level vertices and elements are defined by the order in which they
were inserted into the grid factory}.  Note that this does not mean that
the vertices and elements are traversed in this order by the Level- and
LeafIterators.  What matters are the indices.  Note also that no such
promise is made concerning edges, faces and the like.  Hence it is currently
not possible to read edge and face data along with a grid without some
trickery.

It is also possible to attach data to boundary segments of the coarse grids.
For this, the method \lstinline!Intersection::boundaryId! (which should
really be called \lstinline!boundaryIndex!) returns an index when called
for a boundary intersection.  If the boundary intersection is on level zero
the index is consecutive and zero-starting.  For all other boundary intersections
it is the index of the zero-level ancestor boundary segment of the intersection.

If you have a list of data associated to certain boundary segments of your
coarse grid, you need some control on how the boundary ids are set.  Remember
from Sec.\,\ref{sec:grid_factory} that you can create a grid without mentioning
the boundary at all.  If you do that, the boundary ids are set automatically
by the grid implementation and the exact order is implementation-specific.
If you set boundary segments explicitly using the \lstinline!insertBoundarySegment!
method, then {\em the boundary segments are numbered in the order of their
insertion}.  If you do not set all boundary segments the remaining ones
get automatic, implementation-specific ids.  This is why the second argument
of \lstinline!insertBoundarySegment! is optional: you may want to
influence the ordering of the boundary segments, but leave the boundary
geometry to the grid implementation.  Calling \lstinline!insertBoundarySegment!
with a single argument allows you to do just this.
Peter Bastian's avatar
Peter Bastian committed
1203 1204


Peter Bastian's avatar
Peter Bastian committed
1205 1206 1207
\chapter{Grid implementations}

\section{Using different grids}
Peter Bastian's avatar
Peter Bastian committed
1208

1209
The power of \Dune{} is the possibility of writing one algorithm that
Peter Bastian's avatar
Peter Bastian committed
1210 1211 1212 1213 1214 1215 1216 1217 1218
works on a large variety of grids with different
features. In that chapter we show how the different available grid
classes are instantiated. As an example we create grids for the unit
cube $\Omega=(0,1)^d$ in various dimensions $d$.

The different grid classes have no common interface for instantiation,
they may even have different template parameters. In order make the
examples below easier to write we want to have a class template
\lstinline!UnitCube! that we parametrize with a type \lstinline!T! and
Peter Bastian's avatar
Peter Bastian committed
1219
an integer parameter \lstinline!variant!. \lstinline!T! should be
Peter Bastian's avatar
Peter Bastian committed
1220 1221 1222 1223 1224 1225 1226
one of the available grid types and \lstinline!variant! can be used to
generate different grids (e.~g.~triangular or quadrilateral) for the
same type \lstinline!T!. The advantage of the \lstinline!UnitCube!
template is that the instantiation is hidden from the user.

The definition of the general template is as follows.

1227 1228 1229 1230 1231 1232
\begin{lst}[File dune-grid-howto/unitcube.hh] \mbox{}
\nopagebreak
\lstinputlisting[basicstyle=\ttfamily\scriptsize,numbers=left, 
numberstyle=\tiny, numbersep=5pt]{../unitcube.hh}
\end{lst}

Peter Bastian's avatar
Peter Bastian committed
1233 1234 1235
Instantiation of that template results in a class that throws an
exception when an object is created.

Peter Bastian's avatar
Peter Bastian committed
1236 1237 1238 1239 1240 1241
\minisec{OneDGrid}

The following listing creates a \lstinline!OneDGrid! object. This
class has a constructor without arguments that creates a unit
interval discretized with a single element. \lstinline!OneDGrid!
allows local mesh refinement in one space dimension.
Peter Bastian's avatar
Peter Bastian committed
1242 1243 1244 1245 1246 1247 1248

\begin{lst}[File dune-grid-howto/unitcube\_onedgrid.hh] \mbox{}
\nopagebreak
\lstinputlisting[basicstyle=\ttfamily\scriptsize,numbers=left, 
numberstyle=\tiny, numbersep=5pt]{../unitcube_onedgrid.hh}
\end{lst}

Peter Bastian's avatar
Peter Bastian committed
1249 1250 1251