\section{Mesh refinement and coarsening}%
\label{S:ref.coarse}%
\idx{mesh refinement and coarsening!concepts|(}

In this section, we describe the basic algorithms for the local
refinement and coarsening of simplicial meshes in two and three
dimensions. In 1d the grid is built from intervals, in 2d from
triangles, and in 3d from tetrahedra. We restrict ourselves here to
simplicial meshes, for several reasons:
\begin{enumerate}
\item A simplex is one of the most simple geometric types and
      complex domains may be approximated by a set of simplices quite
      easily.
\item Simplicial meshes allow local refinement (see \figref{F:triangle})
      without the need of non--conforming meshes (hanging nodes),
      parametric elements, or mixture of element types (which is the
      case for quadrilateral meshes, e.g., see \figref{F:rectangle}).
\item Polynomials of any degree are easily represented on a simplex
      using local (barycentric) coordinates.
\end{enumerate}
\begin{figure}[htbp]
\centerline{\includegraphics{EPS/tria}}
\vspace{-2mm}
\caption{Global and local refinement of a triangular mesh.}\label{F:triangle}
\end{figure}
\begin{figure}[htbp]
\centerline{\includegraphics{EPS/rect}}
\vspace{-2mm}
\caption{Local refinements of a rectangular mesh: with hanging nodes, 
         conforming closure using bisected rectangles, and conforming
         closure using triangles. Using a conforming closure with
         rectangles, a local refinement has always global effects up
         to the boundary.}\label{F:rectangle}
\end{figure}

First of all we start with the definition of a simplex, parametric 
simplex and triangulation:


\begin{definition}[Simplex]\label{D:simplex}
a) Let $a_0,\dots,a_d \in \R^n$ be given such that ${a_1 - a_0},\dots,
a_d - a_0$ are linear independent vectors in $\R^n$. The convex set
\begin{equation*}
S = \mbox{conv hull} \{a_0,\dots,a_d\}
\end{equation*}
is called a \emph{$d$--simplex} in $\R^n$.\idx{simplex} For $k < d$ let
\begin{equation*}
S' = \mbox{conv hull} \{a'_0,\dots,a'_k\} \subset \partial S
\end{equation*}
be a $k$--simplex with $a'_0,\dots,a'_k \in  \{a_0,\dots,a_d\}$.
Then $S'$ is called a \emph{$k$--sub--simplex} of $S$. A 
$0$--sub--simplex is called \emph{vertex}, a $1$--sub--simplex 
\emph{edge} and a $2$--sub--simplex \emph{face}.

b) The \emph{standard simplex}\idx{simplex!standard simplex} in $\R^d$ is 
defined by
\begin{equation*}\label{E:Shat}
\Shat = \mbox{conv hull}
\left\{\hat a_0 = 0, \hat a_1 = e_1, \ldots, \hat a_d = e_d\right\},
\end{equation*}
where $e_i$ are the unit vectors in $\R^d$.

c) Let $F_S\colon \Shat \to S \subset \R^n$ be an invertible,
differentiable mapping. Then $S$ is called a \emph{parametric
$d$--simplex}\idx{simplex!parametric simplex} in $\R^n$. The 
$k$--sub--simplices $S'$ of $S$ are given
by the images of the $k$--sub--simplices $\Shat'$ of $\Shat$. Thus,
the vertices $a_0,\dots,a_d$ of $S$ are the points 
$F_S(\hat a_0),\dots, F_S(\hat a_d)$.

d) For a $d$--simplex $S$, we define
\begin{equation*}\label{E:hS,rhoS}
\hS := \mbox{diam}(S) \qquad\mbox{and}\qquad
\rhoS := \sup \{2r;\, B_r \subset S \mbox{ is a $d$--ball of radius } r\},
\end{equation*}
the diameter and inball--diameter of $S$.
\end{definition}

\begin{remark}
Every $d$--simplex $S$ in $\R^n$ is a parametric simplex. 
Defining the matrix $A_S \in \R^{n\times d}$ by
\[
A_S = 
\left[\begin{matrix}
\vdots    &        & \vdots\\
a_1 - a_0 & \cdots & a_d - a_0\\
\vdots    &        & \vdots
\end{matrix}\right],
\]
the parameterization $F_S\colon \Shat \to S$ is given by
\begin{equation}\label{E:FS}
F_S(\xhat) = A_S\,\xhat + a_0.
\end{equation}
Since $F_S$ is affine linear it is differentiable. It is easy to
check that $F_S\colon \Shat \to S$ is invertible and that
$F_S(\hat a_i) = a_i$, $i = 0,\dots,d$ holds.
\end{remark}

\begin{definition}[Triangulation]\label{D:triang}
a) Let $\tria$ be a set of (parametric) $d$--simplices and
define
\[
\Omega = \mbox{interior} \bigcup_{S \in \tria} S \subset \R^n.
\]
We call $\tria$ a \emph{conforming triangulation}\idx{triangulation}
\idx{conforming triangulation} of $\Omega$, \iff 
for two simplices $S_1, S_2 \in \tria$ with $S_1 \ne S_2$ the 
intersection $S_1 \cap S_2$ is either empty or a complete 
$k$--sub--simplex of both $S_1$ and $S_2$ for some
$0 \leq k < d$.

b) Let $\tria_k$, $k \geq 0$, be a sequence of conforming
triangulations. This sequence is called \emph{(shape) regular}, \iff
\begin{equation}\label{E:regular}
\sup_{k \in \N_0}\, \max_{S \in \tria_k\vphantom{\Shat}}\,
 \max_{\xhat\in\Shat}\, \mbox{cond}(DF_S^t(\xhat) \cdot DF_S(\xhat)) < \infty
\end{equation}
holds, where $DF_S$ is the Jacobian of $F_S$ and $\mbox{cond}(A)=\|A\|
\|A^{-1}\|$ denotes the condition number.
\end{definition}

\begin{remark}
For a sequence $\tria_k$, $k \geq 0$, of non--parametric
triangulations the regularity condition \mathref{E:regular} is
equivalent to the condition
\[
\sup_{k \in \N_0} \max_{\vphantom{\Shat}S \in \tria_k} 
                    \frac{\hS}{\rhoS} < \infty.
\]
\end{remark}

In order to construct a sequence of triangulations, we consider the
following situation: An initial (coarse) triangulation $\tria_0$ of the
domain is given. We call it 
\emph{macro triangulation}\idx{macro triangulation}.
It may be generated by hand or by some mesh generation algorithm
(\cite{Schoeberl:97,Shewchuk:96}).

Some (or all) of the simplices are marked for refinement, depending on
some error estimator or indicator. The marked simplices are then
refined, i.e.\ they are cut into smaller ones.  After several
refinements, some other simplices may be marked for
coarsening. Coarsening tries to unite several simplices marked for
coarsening into a bigger simplex. A successive refinement and
coarsening will produce a sequence of triangulations $\tria_0,
\tria_1,\dots$. The refinement of single simplices that we describe in the
next section produces for every simplex of the macro triangulation
only a finite and small number of similarity classes for the resulting
elements. The coarsening is more or less the inverse process of
refinement. This leads to a finite number of similarity classes for
all simplices in the whole sequence of triangulations.

The refinement of non--parametric and parametric simplices is the same
topological operation and can be performed in the same way. The actual
children's shape of parametric elements additionally involves the
children's parameterization. In the following we describe the
refinement and coarsening for triangulations consisting of
non--parametric elements. The refinement of parametric triangulations
can be done in the same way, additionally using given
parameterizations.  Regularity for the constructed sequence can be
obtained with special properties of the parameterizations for parametric
elements and the finite number of similarity classes for simplices.

Marking criteria and marking strategies for refinement and coarsening
are subject of \secref{S:adaptive_methods}.

\subsection{Refinement algorithms for simplicial meshes}%
\label{S:refinement_algorithm}%
\idx{refinement!algorithm}%
\idx{mesh refinement!concepts|(}

For simplicial elements, several refinement algorithms are widely
used. The discussion about and description of these algorithms mainly centers
around refinement in 2d and 3d since refinement in 1d is straight
forward.

One example is regular refinement (``red refinement''), which
divides every triangle into four similar triangles, see
\figref{F:regular_2d}.  The corresponding refinement algorithm in three
dimensions cuts every tetrahedron into eight tetrahedra, and only a
small number of similarity classes occur during successive
refinements, see \cite{Bey:95,Bey:00}. Unfortunately, hanging nodes
arise during local regular refinement. To remove them and create a
conforming mesh, in two dimensions some triangles have to be bisected
(``green closure''). In three dimensions, several types of irregular
refinement are needed for the green closure. This creates more
similarity classes, even in two dimensions. Additionally, these
bisected elements have to be removed before a further refinement of
the mesh, in order to keep the triangulations shape regular.

\begin{figure}[htbp]
\centerline{\includegraphics{EPS/regular_2d}}
\vspace{-2mm}
\caption{Global and local regular refinement of triangles and conforming
         closure by bisection.}\label{F:regular_2d}
\end{figure}

Another possibility is to use bisection of simplices only.
\idx{refinement!bisection} For every
element (triangle or tetrahedron) one of its edges is marked as the
\emph{refinement edge}\idx{refinement!edge}, and the element is refined
into two elements by cutting this edge at its midpoint. There are
several possibilities to choose such a refinement edge for a simplex,
one example is to use the longest edge; Mitchell \cite{Mitchell:89}
compared different approaches.  We focus on an algorithm where the
choice of refinement edges on the macro triangulation prescribes the
refinement edges for all simplices that are created during mesh
refinement. This makes sure that shape regularity of the
triangulations is conserved.

In two dimensions we use the \emph{newest vertex} bisection
\idx{bisection!newest vertex} (in Mitchell's notation) and in three
dimensions the bisection procedure of Kossaczk\'y described in
\cite{Kossaczky:94}\idx{bisection!procedure of Kossaczk\'y}.  We use
the convention, that all vertices of an element are given fixed
\emph{local indices}. Valid indices are 0, 1, for vertices of an
interval, 0, 1, and 2 for vertices of a triangle, and 0, 1, 2, and 3
for vertices of a tetrahedron. Now, the refinement edge for an element
is fixed to be the edge between the vertices with local indices 0 and
1. Here we use the convention that in 1d the element itself is called
``refinement edge''.

During refinement, the new vertex numbers, and thereby the refinement
edges, for the newly created child simplices are prescribed by the
refinement algorithm. For both child elements, the index of the
newly generated vertex at the midpoint of this edge has the highest
local index (2 resp.\ 3 for triangles and tetrahedra). These numbers
are shown in \figref{F:node_numbering_2d} for 1d and 2d, and in
\figref{F:node_numbering_3d} for 3d. In 1d and 2d this numbering
is the same for all refinement levels. In 3d, one has to make some
special arrangements: the numbering of the second child's vertices
depends on the \emph{type} of the element. There exist three
different element types 0, 1, and 2. The type of the elements on the
macro triangulation can be prescribed (usually type 0 tetrahedron).
The type of the refined tetrahedra is recursively given by the
definition that the type of a child element is ((parent's type + 1)
modulo 3). In Figure~\ref{F:node_numbering_3d} we used the following
convention: for the index set $\{\code{1,2,2}\}$ on \code{child[1]} of
a tetrahedron of type \code{0} we use the index \code{1} and for a
tetrahedron of type \code{1} and \code{2} the index \code{2}.
\figref{F:tetra_type} shows successive refinements of a type 0
tetrahedron, producing tetrahedra of types 1, 2, and 0 again.

%\begin{samepage}
\begin{figure}[htbp]%[p]%
\ifletter
\centerline{\includegraphics[width=0.25\textwidth]{EPS/ref_1simplex}\hfil\hfil
            \includegraphics[width=0.55\textwidth]{EPS/ref_tria_v}}
\else
\centerline{\includegraphics[width=0.25\textwidth]{EPS/ref_1simplex}\hfil\hfil
            \includegraphics[width=0.55\textwidth]{EPS/ref_tria_v}}
\fi
\caption{Numbering of nodes on parent and children for intervals and triangles.}
\label{F:node_numbering_2d}
\end{figure}
\begin{figure}[htbp]
\ifletter
\centerline{\includegraphics[scale=0.9]{EPS/ref_tetra_v}}
\else
\centerline{\includegraphics{EPS/ref_tetra_v}}
\fi
\caption{Numbering of nodes on parent and children for
  tetrahedra.}\label{F:node_numbering_3d}
\end{figure}
\begin{figure}[htbp]
\ifletter
\centerline{\includegraphics[scale=0.9]{EPS/ref_tetra_gen}}
\else
\centerline{\includegraphics{EPS/ref_tetra_gen}}
\fi
\caption{Successive refinements of a type 0 tetrahedron.}\label{F:tetra_type}
\end{figure}
%\end{samepage}
\idx{local numbering!vertices}
\idx{refinement!local numbering!vertices}
%\clearpage

By the above algorithm the refinements of simplices are totally
determined by the local vertex numbering on the macro triangulation,
plus a prescribed type for every macro element in three dimensions.
Furthermore, a successive refinement of every macro element only
produces a small number of similarity classes. In case of the
``generic'' triangulation of a (unit) square in 2d and cube in 3d into
two triangles resp.\ six tetrahedra (see
Figure~\ref{F:standard_elements} for a single triangle and tetrahedron
from such a triangulation -- all other elements are generated by
rotation and reflection), the numbering and the definition of the
refinement edge during refinement of the elements guarantee that the
longest edge will always be the refinement edge, see
\figref{F:standard_refined}.

The refinement of a given triangulation now uses the bisection of
\emph{single} elements and can be performed either \emph{iteratively}
or \emph{recursively}. In 1d, bisection only involves the
element which is subject to refinement and thus is a completely
local operation. Both variants of refining a given triangulation
are the same. In 2d and 3d, bisection of a single element usually
involves other elements, resulting in two different algorithms.

For tetrahedra, the first description of such a refinement procedure was given
by B\"ansch using the iterative variant \cite{Baensch:91}. It abandons the
requirement of one to one inter--element adjacencies during the refinement
process and thus needs the intermediate handling of hanging nodes. Two
recursive algorithms, which do not create such hanging nodes and are therefore
easier to implement, are published by Kossaczk\'y \cite{Kossaczky:94} and
Maubach \cite{Maubach:95}.  For a special class of macro triangulations, they
result in exactly the same tetrahedral meshes as the iterative algorithm.

In order to keep the mesh conforming during refinement, the bisection
of an edge is allowed only when such an edge is the refinement edge
for \emph{all} elements which share this edge. Bisection of an edge
and thus of all elements around the edge is the \emph{atomic
refinement operation}\idx{refinement!atomic refinement operation}, 
and no other refinement operation is allowed. See 
Figures~\ref{F:refine_atomic_2d} and \ref{F:refine_atomic_3d} for the 
two and three--dimensional situations.

\begin{figure}[htbp]
\centerline{\includegraphics{EPS/standard}}
\caption{Generic elements in two and three dimensions.}
\label{F:standard_elements}
\end{figure}
\begin{figure}[htbp]
\centerline{\includegraphics{EPS/standard_refined}}
\caption{Refined generic elements in two and three dimensions.}
\label{F:standard_refined}
\end{figure}
\begin{figure}[htbp]
\centerline{\includegraphics{EPS/refine_atomic_2d}}
\vspace{-2mm}
\caption{Atomic refinement operation in two dimensions. The common
  edge is the refinement edge for both triangles.}
\label{F:refine_atomic_2d}
\end{figure}
\begin{figure}[htbp]
\centerline{\includegraphics{EPS/refine_atomic_3d}}
\vspace{-2mm}
\caption{Atomic refinement operation in three dimensions. The common
  edge is the refinement edge for all tetrahedra sharing this
  edge.}\label{F:refine_atomic_3d}
\end{figure}

If an element has to be refined, we have to collect all elements at its
refinement edge. In two dimensions this is either the neighbour opposite
this edge or there is no other element in the case that
the refinement edge belongs to the boundary. In three dimensions we
have to loop around the edge and collect all neighbours at this
edge. If for all collected neighbours the common edge is the refinement edge
too, we can refine the whole patch at the same time by inserting one new
vertex in the midpoint of the common refinement edge and bisecting
every element of the patch. The resulting triangulation then is a
conforming one.

But sometimes the refinement edge of a neighbour is not the common edge.
Such a neighbour is \emph{not compatibly divisible} and we
have to perform first the atomic refinement operation at the
neighbour's refinement edge. In 2d the child of such a neighbour
at the common edge is then compatibly divisible; in 3d such a neighbour 
has to be bisected at most three times and the resulting tetrahedron
at the common edge is then compatibly divisible. The recursive
refinement algorithm now reads
\begin{algorithm}[Recursive refinement of one simplex]
\label{A:recursive_refine}
\begin{algotab}
\> subroutine recursive\_refine($S$, $\tria$)\\
\> \> do\\
\>\> \> $\mathcal{A} := \{S' \in \tria;\, S' 
        \mbox{ is not compatibly divisible with } S\}$\\[1mm]
\>\> \> for all $S' \in \mathcal{A}$ do\\
\>\> \> \> recursive\_refine($S'$, $\tria$);\\
\>\> \> end for\\
\>\> until $\mathcal{A} = \emptyset$  \\[3mm]
\>\> $\mathcal{A} := \{S' \in \tria;\, S' 
       \mbox{ is element at the refinement edge of } S\}$\\[1mm]
\>\> for all $S' \in \mathcal{A}$\\
\>\> \> bisect $S'$ into $S'_0$ and $S'_1$\\
\>\> \> $\tria := \tria\backslash\{S'\} \cup \{S'_0,S'_1\}$\\
\>\> end for
\end{algotab}
\end{algorithm}

In \figref{F:refine_recursive_2d} we show a two--dimensional situation
where recursion is needed. For all triangles, the longest edge is the
refinement edge. Let us assume that triangles A and B are marked for
refinement. Triangle A can be refined at once, as its refinement edge
is a boundary edge. For refinement of triangle B, we have to recursively
refine triangles C and D. Again, triangle D can be directly refined, so
recursion terminates there. This is shown in the second part of the figure.
Back in triangle C, this can now be refined together with its neighbour.
After this, also triangle B can be refined together with its neighbour.
\begin{figure}[htbp]
\centerline{\includegraphics{EPS/refine_recursive_2d}}
\vspace{-2mm}
\caption{Recursive refinement in two dimensions. Triangles A and B are
  initially marked for refinement.}\label{F:refine_recursive_2d}
\end{figure}

The refinement of a given triangulation $\tria$ where some or all 
elements are marked for refinement is then performed by

\begin{algorithm}[Recursive refinement algorithm]\label{A:refine_mesh}
\idx{refinement!recursive refinement algorithm}
\begin{algotab}
\> subroutine refine($\tria$)\\
\> \> for all $S \in \tria$ do\\
\> \> \> if $S$ is marked for refinement\\
\> \> \> \> recursive\_refine($S$, $\tria$)\\
\> \> \> end if\\
\> \> end for\\
\end{algotab}
\end{algorithm}

Since we use recursion, we have to guarantee that recursions terminates.
Kossaczk\'y \cite{Kossaczky:94} and Mitchell \cite{Mitchell:89} proved

\begin{theorem}[Termination and Shape Regularity] The recursive
  refinement algorithm using bisection of single elements fulfills
\begin{enumerate}\itemsep=0pt
\item  The recursion terminates if the macro triangulation satisfies
       certain criteria.
\item  We obtain shape regularity for all elements at all levels.
\end{enumerate}
\end{theorem}

\begin{remark}
1.) A first observation is, that simplices initially not marked for
refinement are bisected, enforced by the refinement of a marked
simplex. This is a necessity to obtain a conforming
triangulation, also for the regular refinement.

2.) It is possible to mark an element for more than one bisection. The
natural choice is to mark a $d$--simplex $S$ for $d$ bisections. After
$d$ refinement steps all original edges of $S$ are bisected. A
simplex $S$ is refined $k$ times by refining the children $S_1$ and
$S_2$ $k-1$ times right after the refinement of $S$.

3.) The recursion does not terminate for an arbitrary choice of
refinement edges on the macro triangulation. In two dimensions, such a
situation is shown in \figref{F:trias_forbidden}. The selected
refinement edges of the triangles are shown by dashed lines. One can
easily see, that there are no patches for the atomic refinement
operation. This triangulation can only be refined if other choices of
refinement edges are made, or by a non--recursive algorithm.
\begin{figure}[htbp]
\centerline{\includegraphics{EPS/trias_forbidden}}
\caption{A macro triangulation where recursion does not stop.}
\label{F:trias_forbidden}
\end{figure}

4.) In two dimensions, for every macro triangulation it is possible to 
choose the refinement edges in such a way that the recursion terminates
(selecting the `longest edge'). In three dimensions the situation is
more complicated. But there is a maybe refined grid such that refinement
edges can be chosen in such a way that recursion terminates
\cite{Kossaczky:94}.
\end{remark}%
\idx{mesh refinement!concepts|)}

\subsection{Coarsening algorithm for simplicial meshes}%
\label{S:coarsening_algorithm}%
\idx{coarsening!algorithm}%
\idx{mesh coarsening!concepts|(}

The coarsening algorithm is more or less the inverse of the refinement
algorithm. The basic idea is to collect all those elements that were
created during the refinement at same time, i.e.\ the parents of these
elements build a compatible refinement patch. The elements may only
be coarsened if \emph{all} involved elements are marked for coarsening
and are of finest level locally, i.e.\ no element is refined further.
The actual coarsening again can be performed in an \emph{atomic
  coarsening operation}\idx{coarsening!atomic coarsening operation}
without the handling of hanging nodes. Information is passed from all
elements onto the parents and the whole patch is coarsened at the same
time by removing the vertex in the parent's common refinement edge
(see Figures~\ref{F:coarse_atomic_2d} and \ref{F:coarse_atomic_3d} for
the atomic coarsening operation in 2d and 3d). This coarsening
operation is completely local in 1d.
\begin{figure}[htbp]
\centerline{\includegraphics[scale=0.45]{EPS/coarse_atomic_2d}}
\vspace{-2mm}
\caption{Atomic coarsening operation in two dimensions.}
\label{F:coarse_atomic_2d}
\end{figure}
\begin{figure}[htbp]
\centerline{\includegraphics[scale=0.45]{EPS/coarse_atomic_3d}}
\vspace{-2mm}
\caption{Atomic coarsening operation in three dimensions.}
\label{F:coarse_atomic_3d}
\end{figure}

During refinement, the bisection of an element can enforce the
refinement of an unmarked element in order to keep the mesh
conforming. During coarsening, an element may only be coarsened
if all elements involved in this operation are marked for 
coarsening. This is the main difference between refinement and coarsening.
In an adaptive method this guarantees that elements with a large
local error indicator marked for refinement are refined and
no element is coarsened where the local error indicator is not
small enough (compare Section~\ref{S:coarsening_strategies}).

Since the coarsening process is the inverse of the refinement,
refinement edges on parent elements are again at their original
position. Thus, further refinement is possible with a terminating
recursion and shape regularity for all resulting elements.

\begin{algorithm}[Local coarsening]\label{A:coarsen}
\begin{algotab}
\> subroutine coarsen\_element($S$, $\tria$)\\
\> \> $\mathcal{A} := \{S' \in \tria;\,
                        S' \mbox{ must not be coarsened with } S\}$\\
\> \> if $\mathcal{A} = \emptyset$\\
\> \> \> for all child pairs $S'_0,S'_1$ at common coarsening edge do\\
\> \> \> \> coarsen $S'_0$ and $S'_1$ into the parent $S'$\\
\> \> \> \> $\tria := \tria\backslash\{S'_0,S'_1\} \cup \{S'\}$\\
\> \> \> end for\\
\> \> end if
\end{algotab}
\end{algorithm}

\noindent
The following routine coarsens as many elements as possible of a
given triangulation $\tria$:

\begin{algorithm}[Coarsening algorithm]\label{A:coarsen_mesh}
\idx{coarsening!coarsening algorithm}
\begin{algotab}
\> subroutine coarsen($\tria$)\\
\> \> for all $S \in \tria$ do\\
\> \> \>  if $S$ is marked for coarsening\\
\> \> \> \> coarsen\_element($S$, $\tria$)\\
\> \> \> end if\\
\> \> end for
\end{algotab}
\end{algorithm}

\begin{remark}\label{R:coarsen}
Also in the coarsening procedure an element can be marked for
several coarsening steps. Usually, the coarsening markers for
all patch elements are cleared if a patch must not be coarsened.
If the patch must not be coarsened because one patch element
is not of locally finest level but may coarsened more than
once, elements stay marked for coarsening. A coarsening
of the finer elements can result in a patch which may then
be coarsened.
\end{remark}

\subsection{Operations during refinement and coarsening}

The refinement and coarsening of elements can be split into
four major steps, which are now described in detail.

\subsubsection{Topological refinement and coarsening}

The actual bisection of an element is performed as follows: the
simplex is cut into two children by inserting a new vertex at the
refinement edge. All objects like this new vertex, or a new edge (in
2d and 3d), or face (in 3d) only have to be created once on the
refinement patch. For example, all elements \emph{share} the new
vertex and two child triangles share a common edge. The refinement
edge is divided into two smaller ones which have to be adjusted to the
respective children.  In 3d all faces inside the patch are bisected
into two smaller ones and this creates an additional edge for each
face. All these objects can be shared by several elements and have to
be assigned to them. If neighbour information is stored, one has to
update such information for elements inside the patch as well as for
neighbours at the patch's boundary.

In the coarsening process the vertex which is shared by all elements
is removed, edges and faces are rejoined and assigned to the
respective parent simplices. Neighbour information has to 
be reinstalled inside the patch and with patch neighbours.%
\idx{mesh coarsening!concepts|)}

\subsubsection{Administration of degrees of freedoms}

Single DOFs can be assigned to a vertex, edge, or face and such a DOF
is shared by all simplices meeting at the vertex, edge, or face
respectively. Finally, there may be DOFs on the element itself, which
are not shared with any other simplex. At each object there may be a
single DOF or several DOFs, even for several finite element spaces.

During refinement new DOFs are created. For each newly created object
(vertex, edge, face, center) we have to create the exact amount
of DOFs, if DOFs are assigned to the object. For example we have to 
create vertex DOFs at the midpoint of the refinement edge, if
DOFs are assigned to a vertex. Again, DOFs must only be created
once for each object and have to be assigned to all simplices
having this object in common.

Additionally, all vectors and matrices using these DOFs have
to be adjusted in size automatically.

\subsubsection{Transfer of geometric data}

Information about the childrens'/parent's shape has to be transformed. During
refinement, for a simplex we only have to calculate the coordinates of the
midpoint of the refinement edge, coordinates of the other vertices stay the
same and can be handed from parent to children.  If the refinement edge
belongs to a curved boundary, the coordinates of the new vertex are calculated
by projecting this midpoint onto the curved boundary. During coarsening, no
calculations have to be done. The $d+1$ vertices of the two children which are
\emph{not} removed are the vertices of the parent.

For the shape of parametric elements, usually more information has to
be calculated. Such information can be stored in a DOF--vector, e.g.,
and may need DOFs on parent and children. Thus, information has to be
assembled after installing the DOFs on the children and before
deleting DOFs on the parent during refinement; during coarsening,
first DOFs on the parent have to be installed, then information can be
assembled, and finally the children's DOFs are removed.

\subsubsection{Transformation of finite element information}%
\idx{coarsening!interpolation of DOF vectors}%
\idx{interpolation of DOF vectors}%
\idx{refinement!interpolation of DOF vectors}%
\idx{interpolation of DOF vectors}%
\idx{coarsening!restriction of DOF vectors}%
\idx{restriction of DOF vectors}%

Using iterative solvers for the (non-) linear systems, a good initial
guess is needed. Usually, the discrete solution from the old grid,
interpolated into the finite element space on the new grid, is a good
initial guess. For piecewise linear finite elements we only have to
compute the value at the newly created node at the midpoint of the
refinement edge and this value is the mean value of the values at the
vertices of the refinement edge:
\[
  \uh({\rm midpoint}) = \frac12(\uh({\rm vertex~0}) + \uh({\rm vertex~1})).
\]
For linear elements an interpolation during coarsening is trivial
since the values at the vertices of the parents stay the same.

For higher order elements more DOFs are involved, but only DOFs
belonging to the refinement/coarsening patch. The interpolation
strongly depends on the local basis functions and it is described
in detail in Section~\ref{S:inter_restrict}. 

Usually during coarsening information is lost (for example, we lose
information about the value of a linear finite element function at the
coarsening edge's midpoint). But linear functionals applied to basis
functions that are calculated on the fine grid and stored in some
coefficient vector can be transformed during coarsening without loss
of information, if the finite element spaces are nested. This is also
described in detail in Section~\ref{S:inter_restrict}. One application
of this procedure is a time discretization, where $L^2$ scalar
products of the new basis functions with the solution
$\uh^\mathrm{old}$ from the last time step appear on the right hand
side of the discrete problem.

Since DOFs can be shared by several elements, these operations are
done on the whole refinement/coarsening patch. This avoids that
coefficients of the interpolant are calculated more than once for a
shared DOF\@. During the restriction of a linear functional we have to
add contribution(s) from one/several DOF(s) to some other
DOF(s). Performing this operation on the whole patch makes it easy to
guarantee that the contribution of a shared DOF is only added once.
\idx{mesh refinement and coarsening!concepts|)}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "alberta-book"
%%% End: