From f5785029575e463cc102f8723578da523b05c8f6 Mon Sep 17 00:00:00 2001 From: hartmann Date: Tue, 20 Nov 2001 15:56:33 +0000 Subject: [PATCH] tex source of the introduction. git-svn-id: https://svn.dealii.org/trunk@5216 0785d39b-7218-0410-832d-ea1e28bc413d --- .../step-12.data/intro.tex | 234 ++++++++++++++++++ 1 file changed, 234 insertions(+) create mode 100644 deal.II/doc/tutorial/chapter-2.step-by-step/step-12.data/intro.tex diff --git a/deal.II/doc/tutorial/chapter-2.step-by-step/step-12.data/intro.tex b/deal.II/doc/tutorial/chapter-2.step-by-step/step-12.data/intro.tex new file mode 100644 index 0000000000..e32783b03e --- /dev/null +++ b/deal.II/doc/tutorial/chapter-2.step-by-step/step-12.data/intro.tex @@ -0,0 +1,234 @@ +\documentclass[11pt]{article} +%\usepackage{a4wide} +\usepackage{amsfonts, graphicx} +\usepackage{amsmath} + +\begin{document} +\subsection{Overview} +This example is devoted to the \emph{discontinuous Galerkin method}, or +in short: DG method. It treats following topics. +\begin{itemize} +\item Discretization of the linear transport equation with the DG method +\item Two different assembling routines of the system matrix based on face terms given +\begin{enumerate} +\item as a sum of integrals over all cell boundaries, and +\item as a sum of integrals over all faces. +\end{enumerate} +\item Time comparison of the two assembling routines. +\end{itemize} + +\subsection{Introduction} +The DG method was first introduced to discretize simple transport +equations. Over the past years DG methods have been applied to a +variety of problems and many different schemes were introduced +employing a big zoo of different convective and diffusive fluxes. As +this example's purpose is to illustrate some implementational issues +of the DG discretization only, here we simply consider the linear +transport equation +\begin{equation}\label{transport-equation} + \nabla\cdot \left\{\beta u\right\}=f \qquad\mbox{in }\Omega, +\end{equation} +subject to the boundary conditions +\[ +u=g\quad\mbox{on }\partial\Omega_-. +\] +Here, $\beta=\beta(x)$ is a vector field, $f$ a source function, $u$ the +(scalar) solution function, $g$ a boundary value function and +\[ +\partial\Omega_-:=\{x\in\partial\Omega, \beta(x)\cdot n(x)<0\} +\] +the inflow boundary of the domain, whereas $n$ denotes the unit outer +normal to boundary $\partial\Omega$ of the domain. This equation, +\eqref{transport-equation}, is the conservative version of the +transport equation already considered in step 9 of this tutorial. +\subsection{Discretization} +To follow the general theory of deriving DG discretizations for purely +hyperbolic equations we first consider the general hyperbolic problem +\[ + \nabla\cdot F(u)=f \qquad\mbox{in }\Omega, +\] +subject to appropriate boundary conditions. Here $F$ denotes the flux +function of the equation under consideration that for in our case, see equation, +\eqref{transport-equation}, is represented by $F(u)=\beta u$. For +deriving the DG discretization we start with a variational, +mesh--dependent formulation of the problem, +\[ + \sum_K\left\{-(F(u),\nabla v)_K+(F(u)\cdot n, v)_{\partial K}\right\}=(f,v)_\Omega, +\] +that originates from \eqref{transport-equation} by multiplication with +a test function and integration by parts on each cell $K$ of the +triangulation. Here $(\cdot, \cdot)_K$ and $(\cdot, \cdot)_{\partial + K}$ simply denote the integrals over the cell and the boundary of +the cell, respectively. To discretize the problem, the functions $u$ +and $v$ are replaced by discrete functions $u_h$ and $v_h$ that in the +case of discontinuous Galerkin methods belong to the space $V_h$ of +discontinuous piecewise polynomial functions of some degree $p$. Due +to the discontinuity of the discrete function $u_h$ on interelement +faces, the flux $F(u)\cdot n$ must be replaced by a \emph{numerical + flux} function $H(u_h, \hat u_h, n)$, where $u_h|_{\partial K}$ +denotes the inner trace (w.r.t. the cell $K$) of $u_h$ and $\hat +u_h|_{\partial K}$ the outer trace, i.e. the value of $u_h$ on the +neighboring cell. Furthermore the numerical flux function $H$, among +other things, is consistent, i.e. +\[ +H(u,u,n)=F(u)\cdot n, +\] +and conservative, i.e. +\begin{equation}\label{conservative} +H(v,w,n)=-H(w,v,-n). +\end{equation} +This yields the following \emph{discontinuous Galerkin + discretization}: find $u_h\in V_h$ such that +\begin{equation}\label{dg-scheme} + \sum_K\left\{-(F(u_h),\nabla v_h)_K+(H(u_h,\hat u_h,n), v_h)_{\partial K}\right\}=(f,v)_\Omega, \quad\forall v_h\in V_h. +\end{equation} +Boundary conditions are realized by replacing $\hat u_h$ on the inflow boundary $\partial\Omega_-$ by the boundary function $g$. +In the special case of the transport equation +\eqref{transport-equation} the numerical flux in its simplest form +is given by +\begin{equation}\label{flux-transport-equation} + H(u_h,\hat u_h,n)(x)=\left\{\begin{array}{ll} + (\beta\cdot n\, u_h)(x),&\mbox{for } \beta(x)\cdot n(x)<0,\\ + (\beta\cdot n\, \hat u_h)(x),&\mbox{for } \beta(x)\cdot n(x)\geq 0. +\end{array} +\right. +\end{equation} +Hence, the discontinuous Galerkin scheme for the transport equation +\eqref{transport-equation} is given by: find $u_h\in V_h$ such that for all $v_h\in V_h$ following equation holds: +\begin{multline}\label{dg-transport} + \sum_K\left\{-(u_h,\beta\cdot\nabla v_h)_K+(\beta\cdot n\, u_h, v_h)_{\partial K_+\setminus\partial\Omega}+(\beta\cdot n\, \hat u_h, v_h)_{\partial K_-\setminus\partial\Omega}\right\}\\ +=(f,v)_\Omega-(\beta\cdot n\, g, v_h)_{\partial\Omega_-}, +\end{multline} +where $\partial K_-:=\{x\in\partial K, \beta(x)\cdot n(x)<0\}$ denotes +the inflow boundary and $\partial K_+=\partial K\setminus \partial +K_-$ the outflow part of cell $K$. This equation will be +refered to as \emph{first version} of the DG method in the following. We +note that after integrating by parts again, we end up with: find +$u_h\in V_h$ such that +\[ + \sum_K\left\{(\nabla\cdot\{\beta u_h\},\nabla v_h)_K-(\beta\cdot n [u_h], v_h)_{\partial K_-}\right\}=(f,v)_\Omega, \quad\forall v_h\in V_h, +\] +where $[u_h]=u_h-\hat u_h$ denotes the jump of the discrete function +between two neighboring cells, that on the boundary of the domain is defined to be $[u_h]=u_h-g$. This is the discontinuous Galerkin +scheme for the transport equation given in its original notation. +Nevertheless, we will base the implementation of the scheme on the form +given by \eqref{dg-scheme} and \eqref{flux-transport-equation}, or +\eqref{dg-transport}, respectively. + +Finally we rewrite \eqref{dg-scheme} in terms of a summation over all faces +where each face $\Gamma=\partial +K\cap\partial \hat K$ between two neighboring cells $K$ and $\hat K$ +occurs twice: Find $u_h\in V_h$ such that +\begin{equation}\label{dg-scheme-faces-long} + -\sum_K(F(u_h),\nabla v_h)_K+\sum_\Gamma\left\{(H(u_h,\hat u_h,n), v_h)_\Gamma+(H(\hat u_h, u_h,-n), \hat v_h)_{\Gamma\setminus\partial\Omega}\right\}=(f,v)_\Omega \quad\forall v_h\in V_h, +\end{equation} +By employing conservativity \eqref{conservative} of the numerical flux +this equation simplifies to: find $u_h\in V_h$ such that +\begin{equation}\label{dg-scheme-faces} + -\sum_K(F(u_h),\nabla v_h)_K+\sum_\Gamma(H(u_h,\hat u_h,n), [v_h])_{\Gamma\setminus\partial\Omega}+\sum_\Gamma(H(u_h,\hat u_h,n), v_h)_{\Gamma\cap\partial\Omega}=(f,v)_\Omega \quad\forall v_h\in V_h. +\end{equation} +Whereas the outer unit normal +$n|_{\partial K}$ is uniquely defined this is not so for $n_\Gamma$. $n_\Gamma$ might be the normal from +either side of the face. Hence, we need to fix the normal $n$ on the face to +be one of the two normals and denote the other normal by +$-n$. This way we get $-n$ in the second face term in +\eqref{dg-scheme-faces-long} that finally produces the minus sign in +the jump $[v_h]$ in equation \eqref{dg-scheme-faces}. + +For the linear transport equation \eqref{transport-equation} this +equation \eqref{dg-scheme-faces} simplifies to +\begin{multline}\label{dg-transport-gamma} + -\sum_K(u_h,\beta\cdot\nabla v_h)_K+\sum_\Gamma\left\{(\beta\cdot n\, u_h, [v_h])_{\Gamma_+\setminus\partial\Omega}+(\beta\cdot n\, \hat u_h, [v_h])_{\Gamma_-\setminus\partial\Omega}\right\}\\ +=(f,v)_\Omega-(\beta\cdot n\, g, v_h)_{\partial\Omega_-}, +\end{multline} +what will be refered to as \emph{second version} of the DG method. +\subsection{Implementation} +As already mentioned at the beginning of this example we will +implement the assembling of the system matrix in two different ways. +The first one will be based on the first version \eqref{dg-transport} +of the DG method that includes a sum of integrals over all cell +boundaries $\partial K$. This is realized by a loop over all cells and +a nested loop over all faces of each cell. Thereby each inner face +$\Gamma=\partial K\cap\partial \hat K$ is treated twice, the first +time when the outer loop treats cell $K$ and the second time when it +treats cell $\hat K$. This way some values like the shape function +values at quadrature points on faces need to be computed twice. + +To overcome this overhead and for comparison, we implement the +assembling of a matrix also in a second and different way. This will +be based on the second version \eqref{dg-transport-gamma} that +includes a sum of integrals over all faces $\Gamma$. Here, several +difficulties occur. +\begin{itemize} +\item As degrees of freedom are associated to cells (and not to faces) + and as a normal is only defined w.r.t a cell adjacent to the face we + cannot simply run over all faces of the triangulation but need to + perform the nested loop over all cells and all faces of each cell + like in the first implementation. This, because in \emph{deal.II} + faces are accessible from cells but not visa versa. +\item Due to the nested loop we arrive twice at each face. In order to + assemble the face terms only once we either need to track which + faces we have treated before, or we introduce a simple rule that decides + which of the two adjacent cells the face should be accessed and + treated from. Here, we employ the second approach and define the + following rule: + \begin{enumerate} + \renewcommand{\labelenumi}{\alph{enumi})} + \item If the two cells adjacent to a face are of the same refinement level we access and treat the face from the cell with lower index. + \item If the two cells are of different refinement levels we access + and treat the face from the coarser cell. + \end{enumerate} +\end{itemize} +Before we start with the description of the code we first introduce +its main ingredients. The main class is called +\emph{DGMethod}. It comprises all basic objects like the +triangulation, the dofhandler, the system matrix and solution vectors. +Furthermore it has got some member functions, the most prominent of +which are the \emph{assemble\_system1} and \emph{assemble\_system2} +functions that implement the two different ways mentioned above for +assembling the system matrix. Within these assembling routines several +different cases must be distinguished while performing the nested +loops over all cells and all faces of each cell and assembling the +respective face terms. While sitting on the current cell and looking +at a specific face there are the cases +\begin{enumerate} +\item face is at boundary, +\item neighboring cell is finer, +\item neighboring cell is of the same refinement level, and +\item neighboring cell is coarser +\end{enumerate} +where `neighboring cell' denotes one of the two cells adjacent to the +face which is not the current cell. In all these cases the assembling +of the face terms are either the same or similar to each other. Hence, +we can implement the assembling of the face terms either by `copy and +paste' (the lazy way, that revenges not later than the scheme or the +equation might want to be changed afterwards) or by calling a separate +function that covers all four cases. To be a bit educational within +this tutorial we perform the latter approach, of course. We go even +further and encapsulate this function and everything that is needed +for assembling the specific equation under consideration within a +class called \emph{DGTransportEquation}. This class includes objects +of all equation--specific functions, as there are the \emph{RHS} and +the \emph{BoundaryValues} class, both derived from the \emph{Function} +class, and the \emph{Beta} class representing the vector field. +Furthermore the \emph{DGTransportEquation} class comprises member +functions \emph{assemble\_face\_terms1} and +\emph{assemble\_face\_terms2} that are invoked by the +\emph{assemble\_system1} and \emph{assemble\_system2} functions of the +\emph{DGMethod}, respectively, and the function +\emph{assemble\_cell\_term} that is the same for both assembling +routines. The \emph{DGTransportEquation} class can then easily be +replaced by a different class that implements a different equation and +a different DG method. Indeed, the implementation of the +\emph{assemble\_system1} and \emph{assemble\_system2} functions will +be general enough to serve for different DG methods, different +equations, even for systems of equations (!) and, under small +modifications, for nonlinear problems. +\end{document} + + + + + + + -- 2.39.5