 |
Reference documentation for deal.II version 9.2.0
|
|
Reference documentation for deal.II version 9.2.0
|
This tutorial depends on step-12.
| Table of contents | |
|---|---|
This example is devoted to anisotropic refinement, which extends to possibilities of local refinement. In most parts, this is a modification of the step-12 tutorial program, we use the same DG method for a linear transport equation. This program will cover the following topics:
The discretization itself will not be discussed, and neither will implementation techniques not specific to anisotropic refinement used here. Please refer to step-12 for this.
Please note, at the moment of writing this tutorial program, anisotropic refinement is only fully implemented for discontinuous Galerkin Finite Elements. This may later change (or may already have).
All the adaptive processes in the preceding tutorial programs were based on isotropic refinement of cells, which cuts all edges in half and forms new cells of these split edges (plus some additional edges, faces and vertices, of course). In deal.II, anisotropic refinement refers to the process of splitting only part of the edges while leaving the others unchanged. Consider a simple square cell, for example:
After the usual refinement it will consist of four children and look like this:
The new anisotropic refinement may take two forms: either we can split the edges which are parallel to the horizontal x-axis, resulting in these two child cells:
or we can split the two edges which run along the y-axis, resulting again in two children, which look that way, however:
All refinement cases of cells are described by an enumeration RefinementPossibilities::Possibilities, and the above anisotropic cases are called cut_x and cut_y for obvious reasons. The isotropic refinement case is called cut_xy in 2D and can be requested from the RefinementCase class via RefinementCase<dim>::isotropic_refinement.
In 3D, there is a third axis which can be split, the z-axis, and thus we have an additional refinement case cut_z here. Isotropic refinement will now refine a cell along the x-, y- and z-axes and thus be referred to as cut_xyz. Additional cases cut_xy, cut_xz and cut_yz exist, which refine a cell along two of the axes, but not along the third one. Given a hex cell with x-axis running to the right, y-axis 'into the page' and z-axis to the top,
we have the isotropic refinement case,
three anisotropic cases which refine only one axis:
and three cases which refine two of the three axes:
For 1D problems, anisotropic refinement can make no difference, as there is only one coordinate direction for a cell, so it is not possible to split it in any other way than isotropically.
Adaptive local refinement is used to obtain fine meshes which are well adapted to solving the problem at hand efficiently. In short, the size of cells which produce a large error is reduced to obtain a better approximation of the solution to the problem at hand. However, a lot of problems contain anisotropic features. Prominent examples are shocks or boundary layers in compressible viscous flows. An efficient mesh approximates these features with cells of higher aspect ratio which are oriented according to the mentioned features. Using only isotropic refinement, the aspect ratios of the original mesh cells are preserved, as they are inherited by the children of a cell. Thus, starting from an isotropic mesh, a boundary layer will be refined in order to catch the rapid variation of the flow field in the wall normal direction, thus leading to cells with very small edge lengths both in normal and tangential direction. Usually, much higher edge lengths in tangential direction and thus significantly less cells could be used without a significant loss in approximation accuracy. An anisotropic refinement process can modify the aspect ratio from mother to child cells by a factor of two for each refinement step. In the course of several refinements, the aspect ratio of the fine cells can be optimized, saving a considerable number of cells and correspondingly degrees of freedom and thus computational resources, memory as well as CPU time.
Most of the time, when we do finite element computations, we only consider one cell at a time, for example to calculate cell contributions to the global matrix, or to interpolate boundary values. However, sometimes we have to look at how cells are related in our algorithms. Relationships between cells come in two forms: neighborship and mother-child relationship. For the case of isotropic refinement, deal.II uses certain conventions (invariants) for cell relationships that are always maintained. For example, a refined cell always has exactly \(2^{dim}\) children. And (except for the 1d case), two neighboring cells may differ by at most one refinement level: they are equally often refined or one of them is exactly once more refined, leaving exactly one hanging node on the common face. Almost all of the time these invariants are only of concern in the internal implementation of the library. However, there are cases where knowledge of them is also relevant to an application program.
In the current context, it is worth noting that the kind of mesh refinement affects some of the most fundamental assumptions. Consequently, some of the usual code found in application programs will need modifications to exploit the features of meshes which were created using anisotropic refinement. For those interested in how deal.II evolved, it may be of interest that the loosening of such invariants required some incompatible changes. For example, the library used to have a member GeometryInfo<dim>::children_per_cell that specified how many children a cell has once it is refined. For isotropic refinement, this number is equal to \(2^{dim}\), as mentioned above. However, for anisotropic refinement, this number does not exist, as is can be either two or four in 2D and two, four or eight in 3D, and the member GeometryInfo<dim>::children_per_cell has consequently been removed. It has now been replaced by GeometryInfo<dim>::max_children_per_cell which specifies the maximum number of children a cell can have. How many children a refined cell has was previously available as static information, but now it depends on the actual refinement state of a cell and can be retrieved using TriaAccessor::n_children(), a call that works equally well for both isotropic and anisotropic refinement. A very similar situation can be found for faces and their subfaces: the pertinent information can be queried using GeometryInfo<dim>::max_children_per_face or face->n_children(), depending on the context.
Another important aspect, and the most important one in this tutorial, is the treatment of neighbor-relations when assembling jump terms on the faces between cells. Looking at the documentation of the assemble_system functions in step-12 we notice, that we need to decide if a neighboring cell is coarser, finer or on the same (refinement) level as our current cell. These decisions do not work in the same way for anisotropic refinement as the information given by the level of a cell is not enough to completely characterize anisotropic cells; for example, are the terminal children of a two-dimensional cell that is first cut in \(x\)-direction and whose children are then cut in \(y\)-direction on level 2, or are they on level 1 as they would be if the cell would have been refined once isotropically, resulting in the same set of finest cells?
After anisotropic refinement, a coarser neighbor is not necessarily exactly one level below ours, but can pretty much have any level relative to the current one; in fact, it can even be on a higher level even though it is coarser. Thus the decisions have to be made on a different basis, whereas the intention of the decisions stays the same.
In the following, we will discuss the cases that can happen when we want to compute contributions to the matrix (or right hand side) of the form
\[ \int_{\partial K} \varphi_i(x) \varphi_j(x) \; dx \]
or similar; remember that we integrate terms like this using the FEFaceValues and FESubfaceValues classes. We will also show how to write code that works for both isotropic and anisotropic refinement:
Finer neighbor: If we are on an active cell and want to integrate over a face \(f\subset \partial K\), the first possibility is that the neighbor behind this face is more refined, i.e. has children occupying only part of the common face. In this case, the face under consideration has to be a refined one, which can determine by asking if (face->has_children()). If this is true, we need to loop over all subfaces and get the neighbors' child behind this subface, so that we can reinit an FEFaceValues object with the neighbor and an FESubfaceValues object with our cell and the respective subface.
For isotropic refinement, this kind is reasonably simple because we know that an invariant of the isotropically refined adaptive meshes in deal.II is that neighbors can only differ by exactly one refinement level. However, this isn't quite true any more for anisotropically refined meshes, in particular in 3d; there, the active cell we are interested on the other side of \(f\) might not actually be a child of our neighbor, but perhaps a grandchild or even a farther offspring. Fortunately, this complexity is hidden in the internals of the library. All we need to do is call the CellAccessor::neighbor_child_on_subface() function. Still, in 3D there are two cases which need special consideration:
If the neighbor is refined more than once anisotropically, it might be that here are not two or four but actually three subfaces to consider. Imagine the following refinement process of the (two-dimensional) face of the (three-dimensional) neighbor cell we are considering: first the face is refined along x, later on only the left subface is refined along y.
Here the number of subfaces is three. It is important to note the subtle differences between, for a face, TriaAccessor::n_children() and TriaAccessor::number_of_children(). The first function returns the number of immediate children, which would be two for the above example, whereas the second returns the number of active offspring (i.e., including children, grandchildren, and further descendants), which is the correct three in the example above. Using face->number_of_children() works for isotropic and anisotropic as well as 2D and 3D cases, so it should always be used. It should be noted that if any of the cells behind the two small subfaces on the left side of the rightmost image is further refined, then the current cell (i.e. the side from which we are viewing this common face) is going to be refined as well: this is so because otherwise the invariant of having only one hanging node per edge would be violated.
It might be, that the neighbor is coarser, but still has children which are finer than our current cell. This situation can occur if two equally coarse cells are refined, where one of the cells has two children at the face under consideration and the other one four. The cells in the next graphic are only separated from each other to show the individual refinement cases.
Here, the left two cells resulted from an anisotropic bisection of the mother cell in \(y\)-direction, whereas the right four cells resulted from a simultaneous anisotropic refinement in both the \(y\)- and \(z\)-directions. The left cell marked with # has two finer neighbors marked with +, but the actual neighbor of the left cell is the complete right mother cell, as the two cells marked with + are finer and their direct mother is the one large cell.
However, fortunately, CellAccessor::neighbor_child_on_subface() takes care of these situations by itself, if you loop over the correct number of subfaces, in the above example this is two. The FESubfaceValues<dim>::reinit function takes care of this too, so that the resulting state is always correct. There is one little caveat, however: For reiniting the neighbors FEFaceValues object you need to know the index of the face that points toward the current cell. Usually you assume that the neighbor you get directly is as coarse or as fine as you, if it has children, thus this information can be obtained with CellAccessor::neighbor_of_neighbor(). If the neighbor is coarser, however, you would have to use the first value in CellAccessor::neighbor_of_coarser_neighbor() instead. In order to make this easy for you, there is CellAccessor::neighbor_face_no() which does the correct thing for you and returns the desired result.
Neighbor is as fine as our cell: After we ruled out all cases in which there are finer children, we only need to decide, whether the neighbor is coarser here. For this, there is the CellAccessor::neighbor_is_coarser() function which returns a boolean. In order to get the relevant case of a neighbor of the same coarseness we would use else if (!cell->neighbor_is_coarser(face_no)). The code inside this block can be left untouched. However, there is one thing to mention here: If we want to use a rule, which cell should assemble certain terms on a given face we might think of the rule presented in step-12. We know that we have to leave out the part about comparing our cell's level with that of the neighbor and replace it with the test for a coarser neighbor presented above. However, we also have to consider the possibility that neighboring cells of same coarseness have the same index (on different levels). Thus we have to include the case where the cells have the same index, and give an additional condition, which of the cells should assemble the terms, e.g. we can choose the cell with lower level. The details of this concept can be seen in the implementation below.
Coarser neighbor: The remaining case is obvious: If there are no refined neighbors and the neighbor is not as fine as the current cell, then it must be coarser. Thus we can leave the old condition phrase, simply using else. The CellAccessor::neighbor_of_coarser_neighbor() function takes care of all the complexity of anisotropic refinement combined with possible non standard face orientation, flip and rotation on general 3D meshes.
When a triangulation is refined, cells which were not flagged for refinement may be refined nonetheless. This is due to additional smoothing algorithms which are either necessary or requested explicitly. In particular, the restriction that there be at most one hanging node on each edge frequently forces the refinement of additional cells neighboring ones that are already finer and are flagged for further refinement.
However, deal.II also implements a number of algorithms that make sure that resulting meshes are smoother than just the bare minimum, for example ensuring that there are no isolated refined cells surrounded by non-refined ones, since the additional degrees of freedom on these islands would almost all be constrained by hanging node constraints. (See the documentation of the Triangulation class and its Triangulation::MeshSmoothing member for more information on mesh smoothing.)
Most of the smoothing algorithms that were originally developed for the isotropic case have been adapted to work in a very similar way for both anisotropic and isotropic refinement. There are two algorithms worth mentioning, however:
MeshSmoothing::limit_level_difference_at_vertices: In an isotropic environment, this algorithm tries to ensure a good approximation quality by reducing the difference in refinement level of cells meeting at a common vertex. However, there is no clear corresponding concept for anisotropic refinement, thus this algorithm may not be used in combination with anisotropic refinement. This restriction is enforced by an assertion which throws an error as soon as the algorithm is called on a triangulation which has been refined anisotropically.
MeshSmoothing::allow_anisotropic_smoothing: If refinement is introduced to limit the number of hanging nodes, the additional cells are often not needed to improve the approximation quality. This is especially true for DG methods. If you set the flag allow_anisotropic_smoothing the smoothing algorithm tries to minimize the number of probably unneeded additional cells by using anisotropic refinement for the smoothing. If you set this smoothing flag you might get anisotropically refined cells, even if you never set a single refinement flag to anisotropic refinement. Be aware that you should only use this flag, if your code respects the possibility of anisotropic meshes. Combined with a suitable anisotropic indicator this flag can help save additional cells and thus effort. Using the benefits of anisotropic refinement requires an indicator to catch anisotropic features of the solution and exploit them for the refinement process. Generally the anisotropic refinement process will consist of several steps:
This approach is similar to the one we have used in step-27 for hp refinement and has the great advantage of flexibility: Any error indicator can be used in the anisotropic process, i.e. if you have quite involved a posteriori goal-oriented error indicators available you can use them as easily as a simple Kelly error estimator. The anisotropic part of the refinement process is not influenced by this choice. Furthermore, simply leaving out the third and forth steps leads to the same isotropic refinement you used to get before any anisotropic changes in deal.II or your application program. As a last advantage, working only on cells flagged for refinement results in a faster evaluation of the anisotropic indicator, which can become noticeable on finer meshes with a lot of cells if the indicator is quite involved.
Here, we use a very simple approach which is only applicable to DG methods. The general idea is quite simple: DG methods allow the discrete solution to jump over the faces of a cell, whereas it is smooth within each cell. Of course, in the limit we expect that the jumps tend to zero as we refine the mesh and approximate the true solution better and better. Thus, a large jump across a given face indicates that the cell should be refined (at least) orthogonally to that face, whereas a small jump does not lead to this conclusion. It is possible, of course, that the exact solution is not smooth and that it also features a jump. In that case, however, a large jump over one face indicates, that this face is more or less parallel to the jump and in the vicinity of it, thus again we would expect a refinement orthogonal to the face under consideration to be effective.
The proposed indicator calculates the average jump \(K_j\), i.e. the mean value of the absolute jump \(|[u]|\) of the discrete solution \(u\) over the two faces \(f_i^j\), \(i=1,2\), \(j=1..d\) orthogonal to coordinate direction \(j\) on the unit cell.
\[ K_j = \frac{\sum_{i=1}^2 \int_{f_i^j}|[u]| dx}{\sum_{i=1}^2 |f_i^j|} . \]
If the average jump in one direction is larger than the average of the jumps in the other directions by a certain factor \(\kappa\), i.e. if \(K_i > \kappa \frac 1{d-1} \sum_{j=1, j\neq i}^d K_j\), the cell is refined only along that particular direction \(i\), otherwise the cell is refined isotropically.
Such a criterion is easily generalized to systems of equations: the absolute value of the jump would be replaced by an appropriate norm of the vector-valued jump.
We solve the linear transport equation presented in step-12. The domain is extended to cover \([-1,1]\times[0,1]\) in 2D, where the flow field \(\beta\) describes a counterclockwise quarter circle around the origin in the right half of the domain and is parallel to the x-axis in the left part of the domain. The inflow boundary is again located at \(x=1\) and along the positive part of the x-axis, and the boundary conditions are chosen as in step-12.
The deal.II include files have already been covered in previous examples and will thus not be further commented on.
And this again is C++:
The last step is as in all previous programs:
The classes describing equation data and the actual assembly of individual terms are almost entirely copied from step-12. We will comment on differences.
The flow field is chosen to be a quarter circle with counterclockwise flow direction and with the origin as midpoint for the right half of the domain with positive \(x\) values, whereas the flow simply goes to the left in the left part of the domain at a velocity that matches the one coming in from the right. In the circular part the magnitude of the flow velocity is proportional to the distance from the origin. This is a difference to step-12, where the magnitude was 1 everywhere. the new definition leads to a linear variation of \(\beta\) along each given face of a cell. On the other hand, the solution \(u(x,y)\) is exactly the same as before.
This declaration of this class is utterly unaffected by our current changes.
Likewise, the constructor of the class as well as the functions assembling the terms corresponding to cell interiors and boundary faces are unchanged from before. The function that assembles face terms between cells also did not change because all it does is operate on two objects of type FEFaceValuesBase (which is the base class of both FEFaceValues and FESubfaceValues). Where these objects come from, i.e. how they are initialized, is of no concern to this function: it simply assumes that the quadrature points on faces or subfaces represented by the two objects correspond to the same points in physical space.
This declaration is much like that of step-12. However, we introduce a new routine (set_anisotropic_flags) and modify another one (refine_grid).
Again we want to use DG elements of degree 1 (but this is only specified in the constructor). If you want to use a DG method of a different degree replace 1 in the constructor by the new degree.
This is new, the threshold value used in the evaluation of the anisotropic jump indicator explained in the introduction. Its value is set to 3.0 in the constructor, but it can easily be changed to a different value greater than 1.
This is a bool flag indicating whether anisotropic refinement shall be used or not. It is set by the constructor, which takes an argument of the same name.
Change here for DG methods of different degrees.
As beta is a linear function, we can choose the degree of the quadrature for which the resulting integration is correct. Thus, we choose to use degree+1 Gauss points, which enables us to integrate exactly polynomials of degree 2*degree+1, enough for all the integrals we will perform in this program.
We proceed with the assemble_system function that implements the DG discretization. This function does the same thing as the assemble_system function from step-12 (but without MeshWorker). The four cases considered for the neighbor-relations of a cell are the same as the isotropic case, namely a) cell is at the boundary, b) there are finer neighboring cells, c) the neighbor is neither coarser nor finer and d) the neighbor is coarser. However, the way in which we decide upon which case we have are modified in the way described in the introduction.
Case (a): The face is at the boundary.
Case (b): This is an internal face and the neighbor is refined (which we can test by asking whether the face of the current cell has children). In this case, we will need to integrate over the "sub-faces", i.e., the children of the face of the current cell.
(There is a slightly confusing corner case: If we are in 1d – where admittedly the current program and its demonstration of anisotropic refinement is not particularly relevant – then the faces between cells are always the same: they are just vertices. In other words, in 1d, we do not want to treat faces between cells of different level differently. The condition face->has_children() we check here ensures this: in 1d, this function always returns false, and consequently in 1d we will not ever go into this if branch. But we will have to come back to this corner case below in case (c).)
We need to know, which of the neighbors faces points in the direction of our cell. Using the neighbor_face_no function we get this information for both coarser and non-coarser neighbors.
Now we loop over all subfaces, i.e. the children and possibly grandchildren of the current face.
To get the cell behind the current subface we can use the neighbor_child_on_subface function. it takes care of all the complicated situations of anisotropic refinement and non-standard faces.
The remaining part of this case is unchanged.
Case (c). We get here if this is an internal face and if the neighbor is not further refined (or, as mentioned above, we are in 1d in which case we get here for every internal face). We then need to decide whether we want to integrate over the current face. If the neighbor is in fact coarser, then we ignore the face and instead handle it when we visit the neighboring cell and look at the current face (except in 1d, where as mentioned above this is not happening):
On the other hand, if the neighbor is more refined, then we have already handled the face in case (b) above (except in 1d). So for 2d and 3d, we just have to decide whether we want to handle a face between cells at the same level from the current side or from the neighboring side. We do this by introducing a tie-breaker: We'll just take the cell with the smaller index (within the current refinement level). In 1d, we take either the coarser cell, or if they are on the same level, the one with the smaller index within that level. This leads to a complicated condition that, hopefully, makes sense given the description above:
Here we know, that the neighbor is not coarser so we can use the usual neighbor_of_neighbor function. However, we could also use the more general neighbor_face_no function.
We do not need to consider a case (d), as those faces are treated 'from the other side within case (b).
For this simple problem we use the simple Richardson iteration again. The solver is completely unaffected by our anisotropic changes.
We refine the grid according to the same simple refinement criterion used in step-12, namely an approximation to the gradient of the solution.
We approximate the gradient,
and scale it to obtain an error indicator.
Then we use this indicator to flag the 30 percent of the cells with highest error indicator to be refined.
Now the refinement flags are set for those cells with a large error indicator. If nothing is done to change this, those cells will be refined isotropically. If the anisotropic flag given to this function is set, we now call the set_anisotropic_flags() function, which uses the jump indicator to reset some of the refinement flags to anisotropic refinement.
Now execute the refinement considering anisotropic as well as isotropic refinement flags.
Once an error indicator has been evaluated and the cells with largest error are flagged for refinement we want to loop over the flagged cells again to decide whether they need isotropic refinement or whether anisotropic refinement is more appropriate. This is the anisotropic jump indicator explained in the introduction.
We want to evaluate the jump over faces of the flagged cells, so we need some objects to evaluate values of the solution on faces.
Now we need to loop over all active cells.
We only need to consider cells which are flagged for refinement.
The four cases of different neighbor relations seen in the assembly routines are repeated much in the same way here.
The neighbor is refined. First we store the information, which of the neighbor's faces points in the direction of our current cell. This property is inherited to the children.
Now we loop over all subfaces,
get an iterator pointing to the cell behind the present subface...
... and reinit the respective FEFaceValues and FESubFaceValues objects.
We obtain the function values
as well as the quadrature weights, multiplied by the Jacobian determinant.
Now we loop over all quadrature points
and integrate the absolute value of the jump of the solution, i.e. the absolute value of the difference between the function value seen from the current cell and the neighboring cell, respectively. We know, that the first two faces are orthogonal to the first coordinate direction on the unit cell, the second two faces are orthogonal to the second coordinate direction and so on, so we accumulate these values into vectors with dim components.
We also sum up the scaled weights to obtain the measure of the face.
Our current cell and the neighbor have the same refinement along the face under consideration. Apart from that, we do much the same as with one of the subcells in the above case.
Now the neighbor is actually coarser. This case is new, in that it did not occur in the assembly routine. Here, we have to consider it, but this is not overly complicated. We simply use the neighbor_of_coarser_neighbor function, which again takes care of anisotropic refinement and non-standard face orientation by itself.
Now we analyze the size of the mean jumps, which we get dividing the jumps by the measure of the respective faces.
Now we loop over the dim coordinate directions of the unit cell and compare the average jump over the faces orthogonal to that direction with the average jumps over faces orthogonal to the remaining direction(s). If the first is larger than the latter by a given factor, we refine only along hat axis. Otherwise we leave the refinement flag unchanged, resulting in isotropic refinement.
The remaining part of the program very much follows the scheme of previous tutorial programs. We output the mesh in VTU format (just as we did in step-1, for example), and the visualization output in VTU format as we almost always do.
Create the rectangular domain.
Adjust the number of cells in different directions to obtain completely isotropic cells for the original mesh.
If you want to run the program in 3D, simply change the following line to const unsigned int dim = 3;.
First, we perform a run with isotropic refinement.
Now we do a second run, this time with anisotropic refinement.
The output of this program consist of the console output, the SVG files containing the grids, and the solutions given in VTU format.
This text output shows the reduction in the number of cells which results from the successive application of anisotropic refinement. After the last refinement step the savings have accumulated so much that almost four times as many cells and thus degrees of freedom are needed in the isotropic case. The time needed for assembly scales with a similar factor.
The first interesting part is of course to see how the meshes look like. On the left are the isotropically refined ones, on the right the anisotropic ones (colors indicate the refinement level of cells):
 |  |
 |  |
 |  |
 |  |
 |  |
 |  |
The other interesting thing is, of course, to see the solution on these two sequences of meshes. Here they are, on the refinement cycles 1 and 4, clearly showing that the solution is indeed composed of discontinuous piecewise polynomials:
 |  |
 |  |
We see, that the solution on the anisotropically refined mesh is very similar to the solution obtained on the isotropically refined mesh. Thus the anisotropic indicator seems to effectively select the appropriate cells for anisotropic refinement.
The pictures also explain why the mesh is refined as it is. In the whole left part of the domain refinement is only performed along the \(y\)-axis of cells. In the right part of the domain the refinement is dominated by isotropic refinement, as the anisotropic feature of the solution - the jump from one to zero - is not well aligned with the mesh where the advection direction takes a turn. However, at the bottom and closest (to the observer) parts of the quarter circle this jumps again becomes more and more aligned with the mesh and the refinement algorithm reacts by creating anisotropic cells of increasing aspect ratio.
It might seem that the necessary alignment of anisotropic features and the coarse mesh can decrease performance significantly for real world problems. That is not wrong in general: If one were, for example, to apply anisotropic refinement to problems in which shocks appear (e.g., the equations solved in step-69), then it many cases the shock is not aligned with the mesh and anisotropic refinement will help little unless one also introduces techniques to move the mesh in alignment with the shocks. On the other hand, many steep features of solutions are due to boundary layers. In those cases, the mesh is already aligned with the anisotropic features because it is of course aligned with the boundary itself, and anisotropic refinement will almost always increase the efficiency of computations on adapted grids for these cases.
1.8.17