1\section{Mesh refinement and coarsening}% 2\label{S:ref.coarse}% 3\idx{mesh refinement and coarsening!concepts|(} 4 5In this section, we describe the basic algorithms for the local 6refinement and coarsening of simplicial meshes in two and three 7dimensions. In 1d the grid is built from intervals, in 2d from 8triangles, and in 3d from tetrahedra. We restrict ourselves here to 9simplicial meshes, for several reasons: 10\begin{enumerate} 11\item A simplex is one of the most simple geometric types and 12 complex domains may be approximated by a set of simplices quite 13 easily. 14\item Simplicial meshes allow local refinement (see \figref{F:triangle}) 15 without the need of non--conforming meshes (hanging nodes), 16 parametric elements, or mixture of element types (which is the 17 case for quadrilateral meshes, e.g., see \figref{F:rectangle}). 18\item Polynomials of any degree are easily represented on a simplex 19 using local (barycentric) coordinates. 20\end{enumerate} 21\begin{figure}[htbp] 22\centerline{\includegraphics{EPS/tria}} 23\vspace{-2mm} 24\caption{Global and local refinement of a triangular mesh.}\label{F:triangle} 25\end{figure} 26\begin{figure}[htbp] 27\centerline{\includegraphics{EPS/rect}} 28\vspace{-2mm} 29\caption{Local refinements of a rectangular mesh: with hanging nodes, 30 conforming closure using bisected rectangles, and conforming 31 closure using triangles. Using a conforming closure with 32 rectangles, a local refinement has always global effects up 33 to the boundary.}\label{F:rectangle} 34\end{figure} 35 36First of all we start with the definition of a simplex, parametric 37simplex and triangulation: 38 39 40\begin{definition}[Simplex]\label{D:simplex} 41a) Let $a_0,\dots,a_d \in \R^n$ be given such that ${a_1 - a_0},\dots, 42a_d - a_0$ are linear independent vectors in $\R^n$. The convex set 43\begin{equation*} 44S = \mbox{conv hull} \{a_0,\dots,a_d\} 45\end{equation*} 46is called a \emph{$d$--simplex} in $\R^n$.\idx{simplex} For $k < d$ let 47\begin{equation*} 48S' = \mbox{conv hull} \{a'_0,\dots,a'_k\} \subset \partial S 49\end{equation*} 50be a $k$--simplex with $a'_0,\dots,a'_k \in \{a_0,\dots,a_d\}$. 51Then $S'$ is called a \emph{$k$--sub--simplex} of $S$. A 52$0$--sub--simplex is called \emph{vertex}, a $1$--sub--simplex 53\emph{edge} and a $2$--sub--simplex \emph{face}. 54 55b) The \emph{standard simplex}\idx{simplex!standard simplex} in $\R^d$ is 56defined by 57\begin{equation*}\label{E:Shat} 58\Shat = \mbox{conv hull} 59\left\{\hat a_0 = 0, \hat a_1 = e_1, \ldots, \hat a_d = e_d\right\}, 60\end{equation*} 61where $e_i$ are the unit vectors in $\R^d$. 62 63c) Let $F_S\colon \Shat \to S \subset \R^n$ be an invertible, 64differentiable mapping. Then $S$ is called a \emph{parametric 65$d$--simplex}\idx{simplex!parametric simplex} in $\R^n$. The 66$k$--sub--simplices $S'$ of $S$ are given 67by the images of the $k$--sub--simplices $\Shat'$ of $\Shat$. Thus, 68the vertices $a_0,\dots,a_d$ of $S$ are the points 69$F_S(\hat a_0),\dots, F_S(\hat a_d)$. 70 71d) For a $d$--simplex $S$, we define 72\begin{equation*}\label{E:hS,rhoS} 73\hS := \mbox{diam}(S) \qquad\mbox{and}\qquad 74\rhoS := \sup \{2r;\, B_r \subset S \mbox{ is a $d$--ball of radius } r\}, 75\end{equation*} 76the diameter and inball--diameter of $S$. 77\end{definition} 78 79\begin{remark} 80Every $d$--simplex $S$ in $\R^n$ is a parametric simplex. 81Defining the matrix $A_S \in \R^{n\times d}$ by 82\[ 83A_S = 84\left[\begin{matrix} 85\vdots & & \vdots\\ 86a_1 - a_0 & \cdots & a_d - a_0\\ 87\vdots & & \vdots 88\end{matrix}\right], 89\] 90the parameterization $F_S\colon \Shat \to S$ is given by 91\begin{equation}\label{E:FS} 92F_S(\xhat) = A_S\,\xhat + a_0. 93\end{equation} 94Since $F_S$ is affine linear it is differentiable. It is easy to 95check that $F_S\colon \Shat \to S$ is invertible and that 96$F_S(\hat a_i) = a_i$, $i = 0,\dots,d$ holds. 97\end{remark} 98 99\begin{definition}[Triangulation]\label{D:triang} 100a) Let $\tria$ be a set of (parametric) $d$--simplices and 101define 102\[ 103\Omega = \mbox{interior} \bigcup_{S \in \tria} S \subset \R^n. 104\] 105We call $\tria$ a \emph{conforming triangulation}\idx{triangulation} 106\idx{conforming triangulation} of $\Omega$, \iff 107for two simplices $S_1, S_2 \in \tria$ with $S_1 \ne S_2$ the 108intersection $S_1 \cap S_2$ is either empty or a complete 109$k$--sub--simplex of both $S_1$ and $S_2$ for some 110$0 \leq k < d$. 111 112b) Let $\tria_k$, $k \geq 0$, be a sequence of conforming 113triangulations. This sequence is called \emph{(shape) regular}, \iff 114\begin{equation}\label{E:regular} 115\sup_{k \in \N_0}\, \max_{S \in \tria_k\vphantom{\Shat}}\, 116 \max_{\xhat\in\Shat}\, \mbox{cond}(DF_S^t(\xhat) \cdot DF_S(\xhat)) < \infty 117\end{equation} 118holds, where $DF_S$ is the Jacobian of $F_S$ and $\mbox{cond}(A)=\|A\| 119\|A^{-1}\|$ denotes the condition number. 120\end{definition} 121 122\begin{remark} 123For a sequence $\tria_k$, $k \geq 0$, of non--parametric 124triangulations the regularity condition \mathref{E:regular} is 125equivalent to the condition 126\[ 127\sup_{k \in \N_0} \max_{\vphantom{\Shat}S \in \tria_k} 128 \frac{\hS}{\rhoS} < \infty. 129\] 130\end{remark} 131 132In order to construct a sequence of triangulations, we consider the 133following situation: An initial (coarse) triangulation $\tria_0$ of the 134domain is given. We call it 135\emph{macro triangulation}\idx{macro triangulation}. 136It may be generated by hand or by some mesh generation algorithm 137(\cite{Schoeberl:97,Shewchuk:96}). 138 139Some (or all) of the simplices are marked for refinement, depending on 140some error estimator or indicator. The marked simplices are then 141refined, i.e.\ they are cut into smaller ones. After several 142refinements, some other simplices may be marked for 143coarsening. Coarsening tries to unite several simplices marked for 144coarsening into a bigger simplex. A successive refinement and 145coarsening will produce a sequence of triangulations $\tria_0, 146\tria_1,\dots$. The refinement of single simplices that we describe in the 147next section produces for every simplex of the macro triangulation 148only a finite and small number of similarity classes for the resulting 149elements. The coarsening is more or less the inverse process of 150refinement. This leads to a finite number of similarity classes for 151all simplices in the whole sequence of triangulations. 152 153The refinement of non--parametric and parametric simplices is the same 154topological operation and can be performed in the same way. The actual 155children's shape of parametric elements additionally involves the 156children's parameterization. In the following we describe the 157refinement and coarsening for triangulations consisting of 158non--parametric elements. The refinement of parametric triangulations 159can be done in the same way, additionally using given 160parameterizations. Regularity for the constructed sequence can be 161obtained with special properties of the parameterizations for parametric 162elements and the finite number of similarity classes for simplices. 163 164Marking criteria and marking strategies for refinement and coarsening 165are subject of \secref{S:adaptive_methods}. 166 167\subsection{Refinement algorithms for simplicial meshes}% 168\label{S:refinement_algorithm}% 169\idx{refinement!algorithm}% 170\idx{mesh refinement!concepts|(} 171 172For simplicial elements, several refinement algorithms are widely 173used. The discussion about and description of these algorithms mainly centers 174around refinement in 2d and 3d since refinement in 1d is straight 175forward. 176 177One example is regular refinement (``red refinement''), which 178divides every triangle into four similar triangles, see 179\figref{F:regular_2d}. The corresponding refinement algorithm in three 180dimensions cuts every tetrahedron into eight tetrahedra, and only a 181small number of similarity classes occur during successive 182refinements, see \cite{Bey:95,Bey:00}. Unfortunately, hanging nodes 183arise during local regular refinement. To remove them and create a 184conforming mesh, in two dimensions some triangles have to be bisected 185(``green closure''). In three dimensions, several types of irregular 186refinement are needed for the green closure. This creates more 187similarity classes, even in two dimensions. Additionally, these 188bisected elements have to be removed before a further refinement of 189the mesh, in order to keep the triangulations shape regular. 190 191\begin{figure}[htbp] 192\centerline{\includegraphics{EPS/regular_2d}} 193\vspace{-2mm} 194\caption{Global and local regular refinement of triangles and conforming 195 closure by bisection.}\label{F:regular_2d} 196\end{figure} 197 198Another possibility is to use bisection of simplices only. 199\idx{refinement!bisection} For every 200element (triangle or tetrahedron) one of its edges is marked as the 201\emph{refinement edge}\idx{refinement!edge}, and the element is refined 202into two elements by cutting this edge at its midpoint. There are 203several possibilities to choose such a refinement edge for a simplex, 204one example is to use the longest edge; Mitchell \cite{Mitchell:89} 205compared different approaches. We focus on an algorithm where the 206choice of refinement edges on the macro triangulation prescribes the 207refinement edges for all simplices that are created during mesh 208refinement. This makes sure that shape regularity of the 209triangulations is conserved. 210 211In two dimensions we use the \emph{newest vertex} bisection 212\idx{bisection!newest vertex} (in Mitchell's notation) and in three 213dimensions the bisection procedure of Kossaczk\'y described in 214\cite{Kossaczky:94}\idx{bisection!procedure of Kossaczk\'y}. We use 215the convention, that all vertices of an element are given fixed 216\emph{local indices}. Valid indices are 0, 1, for vertices of an 217interval, 0, 1, and 2 for vertices of a triangle, and 0, 1, 2, and 3 218for vertices of a tetrahedron. Now, the refinement edge for an element 219is fixed to be the edge between the vertices with local indices 0 and 2201. Here we use the convention that in 1d the element itself is called 221``refinement edge''. 222 223During refinement, the new vertex numbers, and thereby the refinement 224edges, for the newly created child simplices are prescribed by the 225refinement algorithm. For both child elements, the index of the 226newly generated vertex at the midpoint of this edge has the highest 227local index (2 resp.\ 3 for triangles and tetrahedra). These numbers 228are shown in \figref{F:node_numbering_2d} for 1d and 2d, and in 229\figref{F:node_numbering_3d} for 3d. In 1d and 2d this numbering 230is the same for all refinement levels. In 3d, one has to make some 231special arrangements: the numbering of the second child's vertices 232depends on the \emph{type} of the element. There exist three 233different element types 0, 1, and 2. The type of the elements on the 234macro triangulation can be prescribed (usually type 0 tetrahedron). 235The type of the refined tetrahedra is recursively given by the 236definition that the type of a child element is ((parent's type + 1) 237modulo 3). In Figure~\ref{F:node_numbering_3d} we used the following 238convention: for the index set $\{\code{1,2,2}\}$ on \code{child[1]} of 239a tetrahedron of type \code{0} we use the index \code{1} and for a 240tetrahedron of type \code{1} and \code{2} the index \code{2}. 241\figref{F:tetra_type} shows successive refinements of a type 0 242tetrahedron, producing tetrahedra of types 1, 2, and 0 again. 243 244%\begin{samepage} 245\begin{figure}[htbp]%[p]% 246\ifletter 247\centerline{\includegraphics[width=0.25\textwidth]{EPS/ref_1simplex}\hfil\hfil 248 \includegraphics[width=0.55\textwidth]{EPS/ref_tria_v}} 249\else 250\centerline{\includegraphics[width=0.25\textwidth]{EPS/ref_1simplex}\hfil\hfil 251 \includegraphics[width=0.55\textwidth]{EPS/ref_tria_v}} 252\fi 253\caption{Numbering of nodes on parent and children for intervals and triangles.} 254\label{F:node_numbering_2d} 255\end{figure} 256\begin{figure}[htbp] 257\ifletter 258\centerline{\includegraphics[scale=0.9]{EPS/ref_tetra_v}} 259\else 260\centerline{\includegraphics{EPS/ref_tetra_v}} 261\fi 262\caption{Numbering of nodes on parent and children for 263 tetrahedra.}\label{F:node_numbering_3d} 264\end{figure} 265\begin{figure}[htbp] 266\ifletter 267\centerline{\includegraphics[scale=0.9]{EPS/ref_tetra_gen}} 268\else 269\centerline{\includegraphics{EPS/ref_tetra_gen}} 270\fi 271\caption{Successive refinements of a type 0 tetrahedron.}\label{F:tetra_type} 272\end{figure} 273%\end{samepage} 274\idx{local numbering!vertices} 275\idx{refinement!local numbering!vertices} 276%\clearpage 277 278By the above algorithm the refinements of simplices are totally 279determined by the local vertex numbering on the macro triangulation, 280plus a prescribed type for every macro element in three dimensions. 281Furthermore, a successive refinement of every macro element only 282produces a small number of similarity classes. In case of the 283``generic'' triangulation of a (unit) square in 2d and cube in 3d into 284two triangles resp.\ six tetrahedra (see 285Figure~\ref{F:standard_elements} for a single triangle and tetrahedron 286from such a triangulation -- all other elements are generated by 287rotation and reflection), the numbering and the definition of the 288refinement edge during refinement of the elements guarantee that the 289longest edge will always be the refinement edge, see 290\figref{F:standard_refined}. 291 292The refinement of a given triangulation now uses the bisection of 293\emph{single} elements and can be performed either \emph{iteratively} 294or \emph{recursively}. In 1d, bisection only involves the 295element which is subject to refinement and thus is a completely 296local operation. Both variants of refining a given triangulation 297are the same. In 2d and 3d, bisection of a single element usually 298involves other elements, resulting in two different algorithms. 299 300For tetrahedra, the first description of such a refinement procedure was given 301by B\"ansch using the iterative variant \cite{Baensch:91}. It abandons the 302requirement of one to one inter--element adjacencies during the refinement 303process and thus needs the intermediate handling of hanging nodes. Two 304recursive algorithms, which do not create such hanging nodes and are therefore 305easier to implement, are published by Kossaczk\'y \cite{Kossaczky:94} and 306Maubach \cite{Maubach:95}. For a special class of macro triangulations, they 307result in exactly the same tetrahedral meshes as the iterative algorithm. 308 309In order to keep the mesh conforming during refinement, the bisection 310of an edge is allowed only when such an edge is the refinement edge 311for \emph{all} elements which share this edge. Bisection of an edge 312and thus of all elements around the edge is the \emph{atomic 313refinement operation}\idx{refinement!atomic refinement operation}, 314and no other refinement operation is allowed. See 315Figures~\ref{F:refine_atomic_2d} and \ref{F:refine_atomic_3d} for the 316two and three--dimensional situations. 317 318\begin{figure}[htbp] 319\centerline{\includegraphics{EPS/standard}} 320\caption{Generic elements in two and three dimensions.} 321\label{F:standard_elements} 322\end{figure} 323\begin{figure}[htbp] 324\centerline{\includegraphics{EPS/standard_refined}} 325\caption{Refined generic elements in two and three dimensions.} 326\label{F:standard_refined} 327\end{figure} 328\begin{figure}[htbp] 329\centerline{\includegraphics{EPS/refine_atomic_2d}} 330\vspace{-2mm} 331\caption{Atomic refinement operation in two dimensions. The common 332 edge is the refinement edge for both triangles.} 333\label{F:refine_atomic_2d} 334\end{figure} 335\begin{figure}[htbp] 336\centerline{\includegraphics{EPS/refine_atomic_3d}} 337\vspace{-2mm} 338\caption{Atomic refinement operation in three dimensions. The common 339 edge is the refinement edge for all tetrahedra sharing this 340 edge.}\label{F:refine_atomic_3d} 341\end{figure} 342 343If an element has to be refined, we have to collect all elements at its 344refinement edge. In two dimensions this is either the neighbour opposite 345this edge or there is no other element in the case that 346the refinement edge belongs to the boundary. In three dimensions we 347have to loop around the edge and collect all neighbours at this 348edge. If for all collected neighbours the common edge is the refinement edge 349too, we can refine the whole patch at the same time by inserting one new 350vertex in the midpoint of the common refinement edge and bisecting 351every element of the patch. The resulting triangulation then is a 352conforming one. 353 354But sometimes the refinement edge of a neighbour is not the common edge. 355Such a neighbour is \emph{not compatibly divisible} and we 356have to perform first the atomic refinement operation at the 357neighbour's refinement edge. In 2d the child of such a neighbour 358at the common edge is then compatibly divisible; in 3d such a neighbour 359has to be bisected at most three times and the resulting tetrahedron 360at the common edge is then compatibly divisible. The recursive 361refinement algorithm now reads 362\begin{algorithm}[Recursive refinement of one simplex] 363\label{A:recursive_refine} 364\begin{algotab} 365\> subroutine recursive\_refine($S$, $\tria$)\\ 366\> \> do\\ 367\>\> \> $\mathcal{A} := \{S' \in \tria;\, S' 368 \mbox{ is not compatibly divisible with } S\}$\\[1mm] 369\>\> \> for all $S' \in \mathcal{A}$ do\\ 370\>\> \> \> recursive\_refine($S'$, $\tria$);\\ 371\>\> \> end for\\ 372\>\> until $\mathcal{A} = \emptyset$ \\[3mm] 373\>\> $\mathcal{A} := \{S' \in \tria;\, S' 374 \mbox{ is element at the refinement edge of } S\}$\\[1mm] 375\>\> for all $S' \in \mathcal{A}$\\ 376\>\> \> bisect $S'$ into $S'_0$ and $S'_1$\\ 377\>\> \> $\tria := \tria\backslash\{S'\} \cup \{S'_0,S'_1\}$\\ 378\>\> end for 379\end{algotab} 380\end{algorithm} 381 382In \figref{F:refine_recursive_2d} we show a two--dimensional situation 383where recursion is needed. For all triangles, the longest edge is the 384refinement edge. Let us assume that triangles A and B are marked for 385refinement. Triangle A can be refined at once, as its refinement edge 386is a boundary edge. For refinement of triangle B, we have to recursively 387refine triangles C and D. Again, triangle D can be directly refined, so 388recursion terminates there. This is shown in the second part of the figure. 389Back in triangle C, this can now be refined together with its neighbour. 390After this, also triangle B can be refined together with its neighbour. 391\begin{figure}[htbp] 392\centerline{\includegraphics{EPS/refine_recursive_2d}} 393\vspace{-2mm} 394\caption{Recursive refinement in two dimensions. Triangles A and B are 395 initially marked for refinement.}\label{F:refine_recursive_2d} 396\end{figure} 397 398The refinement of a given triangulation $\tria$ where some or all 399elements are marked for refinement is then performed by 400 401\begin{algorithm}[Recursive refinement algorithm]\label{A:refine_mesh} 402\idx{refinement!recursive refinement algorithm} 403\begin{algotab} 404\> subroutine refine($\tria$)\\ 405\> \> for all $S \in \tria$ do\\ 406\> \> \> if $S$ is marked for refinement\\ 407\> \> \> \> recursive\_refine($S$, $\tria$)\\ 408\> \> \> end if\\ 409\> \> end for\\ 410\end{algotab} 411\end{algorithm} 412 413Since we use recursion, we have to guarantee that recursions terminates. 414Kossaczk\'y \cite{Kossaczky:94} and Mitchell \cite{Mitchell:89} proved 415 416\begin{theorem}[Termination and Shape Regularity] The recursive 417 refinement algorithm using bisection of single elements fulfills 418\begin{enumerate}\itemsep=0pt 419\item The recursion terminates if the macro triangulation satisfies 420 certain criteria. 421\item We obtain shape regularity for all elements at all levels. 422\end{enumerate} 423\end{theorem} 424 425\begin{remark} 4261.) A first observation is, that simplices initially not marked for 427refinement are bisected, enforced by the refinement of a marked 428simplex. This is a necessity to obtain a conforming 429triangulation, also for the regular refinement. 430 4312.) It is possible to mark an element for more than one bisection. The 432natural choice is to mark a $d$--simplex $S$ for $d$ bisections. After 433$d$ refinement steps all original edges of $S$ are bisected. A 434simplex $S$ is refined $k$ times by refining the children $S_1$ and 435$S_2$ $k-1$ times right after the refinement of $S$. 436 4373.) The recursion does not terminate for an arbitrary choice of 438refinement edges on the macro triangulation. In two dimensions, such a 439situation is shown in \figref{F:trias_forbidden}. The selected 440refinement edges of the triangles are shown by dashed lines. One can 441easily see, that there are no patches for the atomic refinement 442operation. This triangulation can only be refined if other choices of 443refinement edges are made, or by a non--recursive algorithm. 444\begin{figure}[htbp] 445\centerline{\includegraphics{EPS/trias_forbidden}} 446\caption{A macro triangulation where recursion does not stop.} 447\label{F:trias_forbidden} 448\end{figure} 449 4504.) In two dimensions, for every macro triangulation it is possible to 451choose the refinement edges in such a way that the recursion terminates 452(selecting the `longest edge'). In three dimensions the situation is 453more complicated. But there is a maybe refined grid such that refinement 454edges can be chosen in such a way that recursion terminates 455\cite{Kossaczky:94}. 456\end{remark}% 457\idx{mesh refinement!concepts|)} 458 459\subsection{Coarsening algorithm for simplicial meshes}% 460\label{S:coarsening_algorithm}% 461\idx{coarsening!algorithm}% 462\idx{mesh coarsening!concepts|(} 463 464The coarsening algorithm is more or less the inverse of the refinement 465algorithm. The basic idea is to collect all those elements that were 466created during the refinement at same time, i.e.\ the parents of these 467elements build a compatible refinement patch. The elements may only 468be coarsened if \emph{all} involved elements are marked for coarsening 469and are of finest level locally, i.e.\ no element is refined further. 470The actual coarsening again can be performed in an \emph{atomic 471 coarsening operation}\idx{coarsening!atomic coarsening operation} 472without the handling of hanging nodes. Information is passed from all 473elements onto the parents and the whole patch is coarsened at the same 474time by removing the vertex in the parent's common refinement edge 475(see Figures~\ref{F:coarse_atomic_2d} and \ref{F:coarse_atomic_3d} for 476the atomic coarsening operation in 2d and 3d). This coarsening 477operation is completely local in 1d. 478\begin{figure}[htbp] 479\centerline{\includegraphics[scale=0.45]{EPS/coarse_atomic_2d}} 480\vspace{-2mm} 481\caption{Atomic coarsening operation in two dimensions.} 482\label{F:coarse_atomic_2d} 483\end{figure} 484\begin{figure}[htbp] 485\centerline{\includegraphics[scale=0.45]{EPS/coarse_atomic_3d}} 486\vspace{-2mm} 487\caption{Atomic coarsening operation in three dimensions.} 488\label{F:coarse_atomic_3d} 489\end{figure} 490 491During refinement, the bisection of an element can enforce the 492refinement of an unmarked element in order to keep the mesh 493conforming. During coarsening, an element may only be coarsened 494if all elements involved in this operation are marked for 495coarsening. This is the main difference between refinement and coarsening. 496In an adaptive method this guarantees that elements with a large 497local error indicator marked for refinement are refined and 498no element is coarsened where the local error indicator is not 499small enough (compare Section~\ref{S:coarsening_strategies}). 500 501Since the coarsening process is the inverse of the refinement, 502refinement edges on parent elements are again at their original 503position. Thus, further refinement is possible with a terminating 504recursion and shape regularity for all resulting elements. 505 506\begin{algorithm}[Local coarsening]\label{A:coarsen} 507\begin{algotab} 508\> subroutine coarsen\_element($S$, $\tria$)\\ 509\> \> $\mathcal{A} := \{S' \in \tria;\, 510 S' \mbox{ must not be coarsened with } S\}$\\ 511\> \> if $\mathcal{A} = \emptyset$\\ 512\> \> \> for all child pairs $S'_0,S'_1$ at common coarsening edge do\\ 513\> \> \> \> coarsen $S'_0$ and $S'_1$ into the parent $S'$\\ 514\> \> \> \> $\tria := \tria\backslash\{S'_0,S'_1\} \cup \{S'\}$\\ 515\> \> \> end for\\ 516\> \> end if 517\end{algotab} 518\end{algorithm} 519 520\noindent 521The following routine coarsens as many elements as possible of a 522given triangulation $\tria$: 523 524\begin{algorithm}[Coarsening algorithm]\label{A:coarsen_mesh} 525\idx{coarsening!coarsening algorithm} 526\begin{algotab} 527\> subroutine coarsen($\tria$)\\ 528\> \> for all $S \in \tria$ do\\ 529\> \> \> if $S$ is marked for coarsening\\ 530\> \> \> \> coarsen\_element($S$, $\tria$)\\ 531\> \> \> end if\\ 532\> \> end for 533\end{algotab} 534\end{algorithm} 535 536\begin{remark}\label{R:coarsen} 537Also in the coarsening procedure an element can be marked for 538several coarsening steps. Usually, the coarsening markers for 539all patch elements are cleared if a patch must not be coarsened. 540If the patch must not be coarsened because one patch element 541is not of locally finest level but may coarsened more than 542once, elements stay marked for coarsening. A coarsening 543of the finer elements can result in a patch which may then 544be coarsened. 545\end{remark} 546 547\subsection{Operations during refinement and coarsening} 548 549The refinement and coarsening of elements can be split into 550four major steps, which are now described in detail. 551 552\subsubsection{Topological refinement and coarsening} 553 554The actual bisection of an element is performed as follows: the 555simplex is cut into two children by inserting a new vertex at the 556refinement edge. All objects like this new vertex, or a new edge (in 5572d and 3d), or face (in 3d) only have to be created once on the 558refinement patch. For example, all elements \emph{share} the new 559vertex and two child triangles share a common edge. The refinement 560edge is divided into two smaller ones which have to be adjusted to the 561respective children. In 3d all faces inside the patch are bisected 562into two smaller ones and this creates an additional edge for each 563face. All these objects can be shared by several elements and have to 564be assigned to them. If neighbour information is stored, one has to 565update such information for elements inside the patch as well as for 566neighbours at the patch's boundary. 567 568In the coarsening process the vertex which is shared by all elements 569is removed, edges and faces are rejoined and assigned to the 570respective parent simplices. Neighbour information has to 571be reinstalled inside the patch and with patch neighbours.% 572\idx{mesh coarsening!concepts|)} 573 574\subsubsection{Administration of degrees of freedoms} 575 576Single DOFs can be assigned to a vertex, edge, or face and such a DOF 577is shared by all simplices meeting at the vertex, edge, or face 578respectively. Finally, there may be DOFs on the element itself, which 579are not shared with any other simplex. At each object there may be a 580single DOF or several DOFs, even for several finite element spaces. 581 582During refinement new DOFs are created. For each newly created object 583(vertex, edge, face, center) we have to create the exact amount 584of DOFs, if DOFs are assigned to the object. For example we have to 585create vertex DOFs at the midpoint of the refinement edge, if 586DOFs are assigned to a vertex. Again, DOFs must only be created 587once for each object and have to be assigned to all simplices 588having this object in common. 589 590Additionally, all vectors and matrices using these DOFs have 591to be adjusted in size automatically. 592 593\subsubsection{Transfer of geometric data} 594 595Information about the childrens'/parent's shape has to be transformed. During 596refinement, for a simplex we only have to calculate the coordinates of the 597midpoint of the refinement edge, coordinates of the other vertices stay the 598same and can be handed from parent to children. If the refinement edge 599belongs to a curved boundary, the coordinates of the new vertex are calculated 600by projecting this midpoint onto the curved boundary. During coarsening, no 601calculations have to be done. The $d+1$ vertices of the two children which are 602\emph{not} removed are the vertices of the parent. 603 604For the shape of parametric elements, usually more information has to 605be calculated. Such information can be stored in a DOF--vector, e.g., 606and may need DOFs on parent and children. Thus, information has to be 607assembled after installing the DOFs on the children and before 608deleting DOFs on the parent during refinement; during coarsening, 609first DOFs on the parent have to be installed, then information can be 610assembled, and finally the children's DOFs are removed. 611 612\subsubsection{Transformation of finite element information}% 613\idx{coarsening!interpolation of DOF vectors}% 614\idx{interpolation of DOF vectors}% 615\idx{refinement!interpolation of DOF vectors}% 616\idx{interpolation of DOF vectors}% 617\idx{coarsening!restriction of DOF vectors}% 618\idx{restriction of DOF vectors}% 619 620Using iterative solvers for the (non-) linear systems, a good initial 621guess is needed. Usually, the discrete solution from the old grid, 622interpolated into the finite element space on the new grid, is a good 623initial guess. For piecewise linear finite elements we only have to 624compute the value at the newly created node at the midpoint of the 625refinement edge and this value is the mean value of the values at the 626vertices of the refinement edge: 627\[ 628 \uh({\rm midpoint}) = \frac12(\uh({\rm vertex~0}) + \uh({\rm vertex~1})). 629\] 630For linear elements an interpolation during coarsening is trivial 631since the values at the vertices of the parents stay the same. 632 633For higher order elements more DOFs are involved, but only DOFs 634belonging to the refinement/coarsening patch. The interpolation 635strongly depends on the local basis functions and it is described 636in detail in Section~\ref{S:inter_restrict}. 637 638Usually during coarsening information is lost (for example, we lose 639information about the value of a linear finite element function at the 640coarsening edge's midpoint). But linear functionals applied to basis 641functions that are calculated on the fine grid and stored in some 642coefficient vector can be transformed during coarsening without loss 643of information, if the finite element spaces are nested. This is also 644described in detail in Section~\ref{S:inter_restrict}. One application 645of this procedure is a time discretization, where $L^2$ scalar 646products of the new basis functions with the solution 647$\uh^\mathrm{old}$ from the last time step appear on the right hand 648side of the discrete problem. 649 650Since DOFs can be shared by several elements, these operations are 651done on the whole refinement/coarsening patch. This avoids that 652coefficients of the interpolant are calculated more than once for a 653shared DOF\@. During the restriction of a linear functional we have to 654add contribution(s) from one/several DOF(s) to some other 655DOF(s). Performing this operation on the whole patch makes it easy to 656guarantee that the contribution of a shared DOF is only added once. 657\idx{mesh refinement and coarsening!concepts|)} 658 659%%% Local Variables: 660%%% mode: latex 661%%% TeX-master: "alberta-book" 662%%% End: 663