| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 2003 - 2023 by the deal.II authors |
| 5 |
// |
| 6 |
// This file is part of the deal.II library. |
| 7 |
// |
| 8 |
// Part of the source code is dual licensed under Apache-2.0 WITH |
| 9 |
// LLVM-exception OR LGPL-2.1-or-later. Detailed license information |
| 10 |
// governing the source code and code contributions can be found in |
| 11 |
// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. |
| 12 |
// |
| 13 |
// ------------------------------------------------------------------------ |
| 14 |
|
| 15 |
#ifndef dealii_dof_renumbering_h |
| 16 |
#define dealii_dof_renumbering_h |
| 17 |
|
| 18 |
|
| 19 |
#include <deal.II/base/config.h> |
| 20 |
|
| 21 |
#include <deal.II/base/exceptions.h> |
| 22 |
#include <deal.II/base/point.h> |
| 23 |
|
| 24 |
#include <deal.II/dofs/dof_handler.h> |
| 25 |
|
| 26 |
#include <vector> |
| 27 |
|
| 28 |
DEAL_II_NAMESPACE_OPEN |
| 29 |
|
| 30 |
#ifndef DOXYGEN |
| 31 |
// forward declaration |
| 32 |
template <int, typename, typename> |
| 33 |
class MatrixFree; |
| 34 |
#endif |
| 35 |
|
| 36 |
/** |
| 37 |
* Implementation of a number of renumbering algorithms for the degrees of |
| 38 |
* freedom on a triangulation. The functions in this namespace compute |
| 39 |
* new indices for each degree of freedom of a DoFHandler object, and then call |
| 40 |
* DoFHandler::renumber_dofs(). |
| 41 |
* |
| 42 |
* |
| 43 |
* <h3>Cuthill-McKee like algorithms</h3> |
| 44 |
* |
| 45 |
* Within this class, the Cuthill-McKee algorithm is implemented. It starts at |
| 46 |
* a degree of freedom, searches the other DoFs for those which are coupled |
| 47 |
* with the one we started with and numbers these in a certain way. It then |
| 48 |
* finds the second level of DoFs, namely those that couple with those of the |
| 49 |
* previous level (which were those that coupled with the initial DoF) and |
| 50 |
* numbers these. And so on. For the details of the algorithm, especially the |
| 51 |
* numbering within each level, please see H. R. Schwarz: "Methode der finiten |
| 52 |
* Elemente". The reverse Cuthill-McKee algorithm does the same job, but |
| 53 |
* numbers all elements in the reverse order. |
| 54 |
* |
| 55 |
* These algorithms have one major drawback: they require a good starting |
| 56 |
* point, i.e. the degree of freedom index that will get a new index of zero. |
| 57 |
* The renumbering functions therefore allow the caller to specify such an |
| 58 |
* initial DoF, e.g. by exploiting knowledge of the actual topology of the |
| 59 |
* domain. It is also possible to give several starting indices, which may be |
| 60 |
* used to simulate a simple upstream numbering (by giving the inflow dofs as |
| 61 |
* starting values) or to make preconditioning faster (by letting the |
| 62 |
* Dirichlet boundary indices be starting points). |
| 63 |
* |
| 64 |
* If no starting index is given, one is chosen automatically, namely one with |
| 65 |
* the smallest coordination number (the coordination number is the number of |
| 66 |
* other dofs this dof couples with). This dof is usually located on the |
| 67 |
* boundary of the domain. There is, however, large ambiguity in this when |
| 68 |
* using the hierarchical meshes used in this library, since in most cases the |
| 69 |
* computational domain is not approximated by tilting and deforming elements |
| 70 |
* and by plugging together variable numbers of elements at vertices, but |
| 71 |
* rather by hierarchical refinement. There is therefore a large number of |
| 72 |
* dofs with equal coordination numbers. The renumbering algorithms will |
| 73 |
* therefore not give optimal results. |
| 74 |
* |
| 75 |
* In the book of Schwarz (H.R.Schwarz: Methode der finiten Elemente), it is |
| 76 |
* advised to test many starting points, if possible all with the smallest |
| 77 |
* coordination number and also those with slightly higher numbers. However, |
| 78 |
* this seems only possible for meshes with at most several dozen or a few |
| 79 |
* hundred elements found in small engineering problems of the early 1980s |
| 80 |
* (the second edition was published in 1984), but certainly not with those |
| 81 |
* used in this library, featuring several 10,000 to a few 100,000 elements. |
| 82 |
* |
| 83 |
* |
| 84 |
* <h4>Implementation of renumbering schemes</h4> |
| 85 |
* |
| 86 |
* The renumbering algorithms need quite a lot of memory, since they have to |
| 87 |
* store for each dof with which other dofs it couples. This is done using a |
| 88 |
* SparsityPattern object used to store the sparsity pattern of matrices. It |
| 89 |
* is not useful for the user to do anything between distributing the dofs and |
| 90 |
* renumbering, i.e. the calls to DoFHandler::distribute_dofs and |
| 91 |
* DoFHandler::renumber_dofs should follow each other immediately. If you try |
| 92 |
* to create a sparsity pattern or anything else in between, these will be |
| 93 |
* invalid afterwards. |
| 94 |
* |
| 95 |
* The renumbering may take care of dof-to-dof couplings only induced by |
| 96 |
* eliminating constraints. In addition to the memory consumption mentioned |
| 97 |
* above, this also takes quite some computational time, but it may be |
| 98 |
* switched off upon calling the @p renumber_dofs function. This will then |
| 99 |
* give inferior results, since knots in the graph (representing dofs) are not |
| 100 |
* found to be neighbors even if they would be after condensation. |
| 101 |
* |
| 102 |
* The renumbering algorithms work on a purely algebraic basis, due to the |
| 103 |
* isomorphism between the graph theoretical groundwork underlying the |
| 104 |
* algorithms and binary matrices (matrices of which the entries are binary |
| 105 |
* values) represented by the sparsity patterns. In special, the algorithms do |
| 106 |
* not try to exploit topological knowledge (e.g. corner detection) to find |
| 107 |
* appropriate starting points. This way, however, they work in arbitrary |
| 108 |
* space dimension. |
| 109 |
* |
| 110 |
* If you want to give starting points, you may give a list of dof indices |
| 111 |
* which will form the first step of the renumbering. The dofs of the list |
| 112 |
* will be consecutively numbered starting with zero, i.e. this list is not |
| 113 |
* renumbered according to the coordination number of the nodes. Indices not |
| 114 |
* in the allowed range are deleted. If no index is allowed, the algorithm |
| 115 |
* will search for its own starting point. |
| 116 |
* |
| 117 |
* |
| 118 |
* <h4>Results of renumbering</h4> |
| 119 |
* |
| 120 |
* The renumbering schemes mentioned above do not lead to optimal results. |
| 121 |
* However, after all there is no algorithm that accomplishes this within |
| 122 |
* reasonable time. There are situations where the lack of optimality even |
| 123 |
* leads to worse results than with the original, crude, levelwise numbering |
| 124 |
* scheme; one of these examples is a mesh of four cells of which always those |
| 125 |
* cells are refined which are neighbors to the center (you may call this mesh |
| 126 |
* a `zoom in' mesh). In one such example the bandwidth was increased by about |
| 127 |
* 50 per cent. |
| 128 |
* |
| 129 |
* In most other cases, the bandwidth is reduced significantly. The reduction |
| 130 |
* is the better the less structured the grid is. With one grid where the |
| 131 |
* cells were refined according to a random driven algorithm, the bandwidth |
| 132 |
* was reduced by a factor of six. |
| 133 |
* |
| 134 |
* Using the constraint information usually leads to reductions in bandwidth |
| 135 |
* of 10 or 20 per cent, but may for some very unstructured grids also lead to |
| 136 |
* an increase. You have to weigh the decrease in your case with the time |
| 137 |
* spent to use the constraint information, which usually is several times |
| 138 |
* longer than the `pure' renumbering algorithm. |
| 139 |
* |
| 140 |
* In almost all cases, the renumbering scheme finds a corner to start with. |
| 141 |
* Since there is more than one corner in most grids and since even an |
| 142 |
* interior degree of freedom may be a better starting point, giving the |
| 143 |
* starting point by the user may be a viable way if you have a simple scheme |
| 144 |
* to derive a suitable point (e.g. by successively taking the third child of |
| 145 |
* the cell top left of the coarsest level, taking its third vertex and the |
| 146 |
* dof index thereof, if you want the top left corner vertex). If you do not |
| 147 |
* know beforehand what your grid will look like (e.g. when using adaptive |
| 148 |
* algorithms), searching a best starting point may be difficult, however, and |
| 149 |
* in many cases will not justify the effort. |
| 150 |
* |
| 151 |
* |
| 152 |
* <h3>Component-wise and block-wise numberings</h3> |
| 153 |
* |
| 154 |
* For finite elements composed of several base elements using the FESystem |
| 155 |
* class, or for elements which provide several components themselves, it may |
| 156 |
* be of interest to sort the DoF indices by component. This will then bring |
| 157 |
* out the block matrix structure, since otherwise the degrees of freedom are |
| 158 |
* numbered cell-wise without taking into account that they may belong to |
| 159 |
* different components. For example, one may want to sort degree of freedom |
| 160 |
* for a Stokes discretization so that we first get all velocities and then |
| 161 |
* all the pressures so that the resulting matrix naturally decomposes into a |
| 162 |
* $2\times 2$ system. |
| 163 |
* |
| 164 |
* This kind of numbering may be obtained by calling the |
| 165 |
* component_wise() function of this class. Since it does not touch |
| 166 |
* the order of indices within each component, it may be worthwhile to |
| 167 |
* first renumber using the Cuthill-McKee or a similar algorithm and |
| 168 |
* afterwards renumbering component-wise. This will bring out the |
| 169 |
* matrix structure and additionally have a good numbering within each |
| 170 |
* block. |
| 171 |
* |
| 172 |
* The component_wise() function allows not only to honor enumeration based on |
| 173 |
* vector components, but also allows to group together vector components into |
| 174 |
* "blocks" using a defaulted argument to the various |
| 175 |
* DoFRenumbering::component_wise() functions (see |
| 176 |
* @ref GlossComponent |
| 177 |
* vs |
| 178 |
* @ref GlossBlock |
| 179 |
* for a description of the difference). The blocks designated through this |
| 180 |
* argument may, but do not have to be, equal to the blocks that the finite |
| 181 |
* element reports. For example, a typical Stokes element would be |
| 182 |
* @code |
| 183 |
* FESystem<dim> stokes_fe (FE_Q<dim>(2), dim, // dim velocities |
| 184 |
* FE_Q<dim>(1), 1); // one pressure |
| 185 |
* @endcode |
| 186 |
* This element has <code>dim+1</code> vector components and equally many |
| 187 |
* blocks. However, one may want to consider the velocities as one logical |
| 188 |
* block so that all velocity degrees of freedom are enumerated the same way, |
| 189 |
* independent of whether they are $x$- or $y$-velocities. This is done, for |
| 190 |
* example, in step-20 and step-22 as well as several other tutorial programs. |
| 191 |
* |
| 192 |
* On the other hand, if you really want to use block structure reported by |
| 193 |
* the finite element itself (a case that is often the case if you have finite |
| 194 |
* elements that have multiple vector components, e.g. the FE_RaviartThomas or |
| 195 |
* FE_Nedelec elements) then you can use the DoFRenumbering::block_wise |
| 196 |
* instead of the DoFRenumbering::component_wise functions. |
| 197 |
* |
| 198 |
* |
| 199 |
* <h3>Cell-wise numbering</h3> |
| 200 |
* |
| 201 |
* Given an ordered vector of cells, the function cell_wise() sorts the |
| 202 |
* degrees of freedom such that degrees on earlier cells of this vector will |
| 203 |
* occur before degrees on later cells. |
| 204 |
* |
| 205 |
* This rule produces a well-defined ordering for discontinuous Galerkin |
| 206 |
* methods (FE_DGP, FE_DGQ). For continuous methods, we use the additional |
| 207 |
* rule that each degree of freedom is ordered according to the first cell in |
| 208 |
* the ordered vector it belongs to. |
| 209 |
* |
| 210 |
* Applications of this scheme are downstream() and clock_wise_dg(). The first |
| 211 |
* orders the cells according to a downstream direction and then applies |
| 212 |
* cell_wise(). |
| 213 |
* |
| 214 |
* @note For DG elements, the internal numbering in each cell remains |
| 215 |
* unaffected. This cannot be guaranteed for continuous elements anymore, |
| 216 |
* since degrees of freedom shared with an earlier cell will be accounted for |
| 217 |
* by the other cell. |
| 218 |
* |
| 219 |
* |
| 220 |
* <h3>Random renumbering</h3> |
| 221 |
* |
| 222 |
* The random() function renumbers degrees of freedom randomly. This function |
| 223 |
* is probably seldom of use, except to check the dependence of solvers |
| 224 |
* (iterative or direct ones) on the numbering of the degrees of freedom. |
| 225 |
* |
| 226 |
* |
| 227 |
* <h3>Renumbering DoFs for faster matrix-free computations</h3> |
| 228 |
* |
| 229 |
* The MatrixFree class provides optimized algorithms for interleaving |
| 230 |
* operations on vectors before and after the access of the vector data in the |
| 231 |
* respective loops. The algorithm matrix_free_data_locality() makes sure |
| 232 |
* that all unknowns with a short distance between the first and last access |
| 233 |
* are grouped together, in order to increase the spatial data locality. |
| 234 |
* |
| 235 |
* |
| 236 |
* <h3>A comparison of reordering strategies</h3> |
| 237 |
* |
| 238 |
* As a benchmark of comparison, let us consider what the different sparsity |
| 239 |
* patterns produced by the various algorithms when using the $Q_2^d\times |
| 240 |
* Q_1$ element combination typically employed in the discretization of Stokes |
| 241 |
* equations, when used on the mesh obtained in step-22 after one adaptive |
| 242 |
* mesh refinement in 3d. The space dimension together with the coupled finite |
| 243 |
* element leads to a rather dense system matrix with, on average around 180 |
| 244 |
* nonzero entries per row. After applying each of the reordering strategies |
| 245 |
* shown below, the degrees of freedom are also sorted using |
| 246 |
* DoFRenumbering::component_wise into velocity and pressure groups; this |
| 247 |
* produces the $2\times 2$ block structure seen below with the large |
| 248 |
* velocity-velocity block at top left, small pressure-pressure block at |
| 249 |
* bottom right, and coupling blocks at top right and bottom left. |
| 250 |
* |
| 251 |
* The goal of reordering strategies is to improve the preconditioner. In |
| 252 |
* step-22 we use a SparseILU to preconditioner for the velocity-velocity |
| 253 |
* block at the top left. The quality of the preconditioner can then be |
| 254 |
* measured by the number of CG iterations required to solve a linear system |
| 255 |
* with this block. For some of the reordering strategies below we record this |
| 256 |
* number for adaptive refinement cycle 3, with 93176 degrees of freedom; |
| 257 |
* because we solve several linear systems with the same matrix in the Schur |
| 258 |
* complement, the average number of iterations is reported. The lower the |
| 259 |
* number the better the preconditioner and consequently the better the |
| 260 |
* renumbering of degrees of freedom is suited for this task. We also state |
| 261 |
* the run-time of the program, in part determined by the number of iterations |
| 262 |
* needed, for the first 4 cycles on one of our machines. Note that the |
| 263 |
* reported times correspond to the run time of the entire program, not just |
| 264 |
* the affected solver; if a program runs twice as fast with one particular |
| 265 |
* ordering than with another one, then this means that the actual solver is |
| 266 |
* actually several times faster. |
| 267 |
* |
| 268 |
* <table> <tr> <td> |
| 269 |
* @image html "reorder_sparsity_step_31_original.png" |
| 270 |
* </td> <td> |
| 271 |
* @image html "reorder_sparsity_step_31_random.png" |
| 272 |
* </td> <td> |
| 273 |
* @image html "reorder_sparsity_step_31_deal_cmk.png" |
| 274 |
* </td> </tr> <tr> <td> Enumeration as produced by deal.II's |
| 275 |
* DoFHandler::distribute_dofs function and no further reordering apart from |
| 276 |
* the component-wise one. |
| 277 |
* |
| 278 |
* With this renumbering, we needed an average of 92.2 iterations for the |
| 279 |
* testcase outlined above, and a runtime of 7min53s. </td> <td> Random |
| 280 |
* enumeration as produced by applying DoFRenumbering::random after calling |
| 281 |
* DoFHandler::distribute_dofs. This enumeration produces nonzero entries in |
| 282 |
* matrices pretty much everywhere, appearing here as an entirely unstructured |
| 283 |
* matrix. |
| 284 |
* |
| 285 |
* With this renumbering, we needed an average of 71 iterations for the |
| 286 |
* testcase outlined above, and a runtime of 10min55s. The longer runtime |
| 287 |
* despite less iterations compared to the default ordering may be due to the |
| 288 |
* fact that computing and applying the ILU requires us to jump back and forth |
| 289 |
* all through memory due to the lack of localization of matrix entries around |
| 290 |
* the diagonal; this then leads to many cache misses and consequently bad |
| 291 |
* timings. </td> <td> Cuthill-McKee enumeration as produced by calling the |
| 292 |
* deal.II implementation of the algorithm provided by |
| 293 |
* DoFRenumbering::Cuthill_McKee after DoFHandler::distribute_dofs. |
| 294 |
* |
| 295 |
* With this renumbering, we needed an average of 57.3 iterations for the |
| 296 |
* testcase outlined above, and a runtime of 6min10s. </td> </td> </tr> |
| 297 |
* |
| 298 |
* <tr> <td> |
| 299 |
* @image html "reorder_sparsity_step_31_boost_cmk.png" |
| 300 |
* </td> <td> |
| 301 |
* @image html "reorder_sparsity_step_31_boost_king.png" |
| 302 |
* </td> <td> |
| 303 |
* @image html "reorder_sparsity_step_31_boost_md.png" |
| 304 |
* </td> </tr> <tr> <td> Cuthill- McKee enumeration as produced by calling the |
| 305 |
* BOOST implementation of the algorithm provided by |
| 306 |
* DoFRenumbering::boost::Cuthill_McKee after DoFHandler::distribute_dofs. |
| 307 |
* |
| 308 |
* With this renumbering, we needed an average of 51.7 iterations for the |
| 309 |
* testcase outlined above, and a runtime of 5min52s. </td> <td> King |
| 310 |
* enumeration as produced by calling the BOOST implementation of the |
| 311 |
* algorithm provided by DoFRenumbering::boost::king_ordering after |
| 312 |
* DoFHandler::distribute_dofs. The sparsity pattern appears denser than with |
| 313 |
* BOOST's Cuthill-McKee algorithm; however, this is only an illusion: the |
| 314 |
* number of nonzero entries is the same, they are simply not as well |
| 315 |
* clustered. |
| 316 |
* |
| 317 |
* With this renumbering, we needed an average of 51.0 iterations for the |
| 318 |
* testcase outlined above, and a runtime of 5min03s. Although the number of |
| 319 |
* iterations is only slightly less than with BOOST's Cuthill-McKee |
| 320 |
* implementation, runtime is significantly less. This, again, may be due to |
| 321 |
* cache effects. As a consequence, this is the algorithm best suited to the |
| 322 |
* testcase, and is in fact used in step-22. </td> <td> Minimum degree |
| 323 |
* enumeration as produced by calling the BOOST implementation of the |
| 324 |
* algorithm provided by DoFRenumbering::boost::minimum_degree after |
| 325 |
* DoFHandler::distribute_dofs. The minimum degree algorithm does not attempt |
| 326 |
* to minimize the bandwidth of a matrix but to minimize the amount of fill-in |
| 327 |
* a LU decomposition would produce, i.e. the number of places in the matrix |
| 328 |
* that would be occupied by elements of an LU decomposition that are not |
| 329 |
* already occupied by elements of the original matrix. The resulting sparsity |
| 330 |
* pattern obviously has an entirely different structure than the ones |
| 331 |
* produced by algorithms trying to minimize the bandwidth. |
| 332 |
* |
| 333 |
* With this renumbering, we needed an average of 58.9 iterations for the |
| 334 |
* testcase outlined above, and a runtime of 6min11s. </td> </tr> |
| 335 |
* |
| 336 |
* <tr> <td> |
| 337 |
* @image html "reorder_sparsity_step_31_downstream.png" |
| 338 |
* </td> <td> </td> <td> </td> </tr> <tr> <td> Downstream enumeration using |
| 339 |
* DoFRenumbering::downstream using a direction that points diagonally through |
| 340 |
* the domain. |
| 341 |
* |
| 342 |
* With this renumbering, we needed an average of 90.5 iterations for the |
| 343 |
* testcase outlined above, and a runtime of 7min05s. </td> <td> </td> <td> |
| 344 |
* </td> </tr> </table> |
| 345 |
* |
| 346 |
* |
| 347 |
* <h3>Multigrid DoF numbering</h3> |
| 348 |
* |
| 349 |
* Most of the algorithms listed above also work on multigrid degree of |
| 350 |
* freedom numberings. Refer to the actual function declarations to get more |
| 351 |
* information on this. |
| 352 |
* |
| 353 |
* @ingroup dofs |
| 354 |
*/ |
| 355 |
namespace DoFRenumbering |
| 356 |
{ |
| 357 |
/** |
| 358 |
* Direction based comparator for cell iterators: it returns @p true if the |
| 359 |
* center of the second cell is downstream of the center of the first one |
| 360 |
* with respect to the direction given to the constructor. |
| 361 |
*/ |
| 362 |
template <class Iterator, int dim> |
| 363 |
struct CompareDownstream |
| 364 |
{ |
| 365 |
/** |
| 366 |
* Constructor. |
| 367 |
*/ |
| 368 |
CompareDownstream(const Tensor<1, dim> &dir) |
| 369 |
: dir(dir) |
| 370 |
{} |
| 371 |
/** |
| 372 |
* Return true if c1 less c2. |
| 373 |
*/ |
| 374 |
bool |
| 375 |
operator()(const Iterator &c1, const Iterator &c2) const |
| 376 |
{ |
| 377 |
const Tensor<1, dim> diff = c2->center() - c1->center(); |
| 378 |
return (diff * dir > 0); |
| 379 |
} |
| 380 |
|
| 381 |
private: |
| 382 |
/** |
| 383 |
* Flow direction. |
| 384 |
*/ |
| 385 |
const Tensor<1, dim> dir; |
| 386 |
}; |
| 387 |
|
| 388 |
|
| 389 |
/** |
| 390 |
* Point based comparator for downstream directions: it returns @p true if |
| 391 |
* the second point is downstream of the first one with respect to the |
| 392 |
* direction given to the constructor. If the points are the same with |
| 393 |
* respect to the downstream direction, the point with the lower DoF number |
| 394 |
* is considered smaller. |
| 395 |
*/ |
| 396 |
template <int dim> |
| 397 |
struct ComparePointwiseDownstream |
| 398 |
{ |
| 399 |
/** |
| 400 |
* Constructor. |
| 401 |
*/ |
| 402 |
ComparePointwiseDownstream(const Tensor<1, dim> &dir) |
| 403 |
: dir(dir) |
| 404 |
{} |
| 405 |
/** |
| 406 |
* Return true if c1 less c2. |
| 407 |
*/ |
| 408 |
bool |
| 409 |
operator()(const std::pair<Point<dim>, types::global_dof_index> &c1, |
| 410 |
const std::pair<Point<dim>, types::global_dof_index> &c2) const |
| 411 |
{ |
| 412 |
const Tensor<1, dim> diff = c2.first - c1.first; |
| 413 |
return (diff * dir > 0 || (diff * dir == 0 && c1.second < c2.second)); |
| 414 |
} |
| 415 |
|
| 416 |
private: |
| 417 |
/** |
| 418 |
* Flow direction. |
| 419 |
*/ |
| 420 |
const Tensor<1, dim> dir; |
| 421 |
}; |
| 422 |
|
| 423 |
|
| 424 |
|
| 425 |
/** |
| 426 |
* A namespace for the implementation of some renumbering algorithms based |
| 427 |
* on algorithms implemented in the Boost Graph Library (BGL) by Jeremy Siek |
| 428 |
* and others. |
| 429 |
* |
| 430 |
* While often slightly slower to compute, the algorithms using BOOST often |
| 431 |
* lead to matrices with smaller bandwidths and sparse ILUs based on this |
| 432 |
* numbering are therefore more efficient. |
| 433 |
* |
| 434 |
* For a comparison of these algorithms with the ones defined in |
| 435 |
* DoFRenumbering, see the comparison section in the documentation of the |
| 436 |
* DoFRenumbering namespace. |
| 437 |
*/ |
| 438 |
namespace boost |
| 439 |
{ |
| 440 |
/** |
| 441 |
* Renumber the degrees of freedom according to the Cuthill-McKee method, |
| 442 |
* eventually using the reverse numbering scheme. |
| 443 |
* |
| 444 |
* See the general documentation of the parent class for details on the |
| 445 |
* different methods. |
| 446 |
* |
| 447 |
* As an example of the results of this algorithm, take a look at the |
| 448 |
* comparison of various algorithms in the documentation of the |
| 449 |
* DoFRenumbering namespace. |
| 450 |
*/ |
| 451 |
template <int dim, int spacedim> |
| 452 |
void |
| 453 |
Cuthill_McKee(DoFHandler<dim, spacedim> &dof_handler, |
| 454 |
const bool reversed_numbering = false, |
| 455 |
const bool use_constraints = false); |
| 456 |
|
| 457 |
/** |
| 458 |
* Compute the renumbering vector needed by the Cuthill_McKee() function. |
| 459 |
* Does not perform the renumbering on the DoFHandler dofs but returns the |
| 460 |
* renumbering vector. |
| 461 |
*/ |
| 462 |
template <int dim, int spacedim> |
| 463 |
void |
| 464 |
compute_Cuthill_McKee(std::vector<types::global_dof_index> &new_dof_indices, |
| 465 |
const DoFHandler<dim, spacedim> &, |
| 466 |
const bool reversed_numbering = false, |
| 467 |
const bool use_constraints = false); |
| 468 |
|
| 469 |
/** |
| 470 |
* Renumber the degrees of freedom based on the BOOST implementation of |
| 471 |
* the King algorithm. This often results in slightly larger (by a few |
| 472 |
* percent) bandwidths than the Cuthill-McKee algorithm, but sparse ILUs |
| 473 |
* are often slightly (also by a few percent) better preconditioners. |
| 474 |
* |
| 475 |
* As an example of the results of this algorithm, take a look at the |
| 476 |
* comparison of various algorithms in the documentation of the |
| 477 |
* DoFRenumbering namespace. |
| 478 |
* |
| 479 |
* This algorithm is used in step-22. |
| 480 |
*/ |
| 481 |
template <int dim, int spacedim> |
| 482 |
void |
| 483 |
king_ordering(DoFHandler<dim, spacedim> &dof_handler, |
| 484 |
const bool reversed_numbering = false, |
| 485 |
const bool use_constraints = false); |
| 486 |
|
| 487 |
/** |
| 488 |
* Compute the renumbering for the King algorithm but do not actually |
| 489 |
* renumber the degrees of freedom in the DoF handler argument. |
| 490 |
*/ |
| 491 |
template <int dim, int spacedim> |
| 492 |
void |
| 493 |
compute_king_ordering(std::vector<types::global_dof_index> &new_dof_indices, |
| 494 |
const DoFHandler<dim, spacedim> &, |
| 495 |
const bool reversed_numbering = false, |
| 496 |
const bool use_constraints = false); |
| 497 |
|
| 498 |
/** |
| 499 |
* Renumber the degrees of freedom based on the BOOST implementation of |
| 500 |
* the minimum degree algorithm. Unlike the Cuthill-McKee algorithm, this |
| 501 |
* algorithm does not attempt to minimize the bandwidth of a matrix but to |
| 502 |
* minimize the amount of fill-in when doing an LU decomposition. It may |
| 503 |
* sometimes yield better ILUs because of this property. |
| 504 |
* |
| 505 |
* As an example of the results of this algorithm, take a look at the |
| 506 |
* comparison of various algorithms in the documentation of the |
| 507 |
* DoFRenumbering namespace. |
| 508 |
*/ |
| 509 |
template <int dim, int spacedim> |
| 510 |
void |
| 511 |
minimum_degree(DoFHandler<dim, spacedim> &dof_handler, |
| 512 |
const bool reversed_numbering = false, |
| 513 |
const bool use_constraints = false); |
| 514 |
|
| 515 |
/** |
| 516 |
* Compute the renumbering for the minimum degree algorithm but do not |
| 517 |
* actually renumber the degrees of freedom in the DoF handler argument. |
| 518 |
*/ |
| 519 |
template <int dim, int spacedim> |
| 520 |
void |
| 521 |
compute_minimum_degree( |
| 522 |
std::vector<types::global_dof_index> &new_dof_indices, |
| 523 |
const DoFHandler<dim, spacedim> &, |
| 524 |
const bool reversed_numbering = false, |
| 525 |
const bool use_constraints = false); |
| 526 |
} // namespace boost |
| 527 |
|
| 528 |
/** |
| 529 |
* Renumber the degrees of freedom according to the Cuthill-McKee method, |
| 530 |
* possibly using the reverse numbering scheme. |
| 531 |
* |
| 532 |
* See the general documentation of this class for details on the different |
| 533 |
* methods. |
| 534 |
* |
| 535 |
* As an example of the results of this algorithm, take a look at the |
| 536 |
* comparison of various algorithms in the documentation of the |
| 537 |
* DoFRenumbering namespace. |
| 538 |
* |
| 539 |
* @param dof_handler The DoFHandler object to work on. |
| 540 |
* @param reversed_numbering Whether to use the original Cuthill-McKee |
| 541 |
* algorithm, or to reverse the ordering. |
| 542 |
* @param use_constraints Whether or not to use hanging node constraints in |
| 543 |
* determining the reordering of degrees of freedom. |
| 544 |
* @param starting_indices A set of degrees of freedom that form the first |
| 545 |
* level of renumbered degrees of freedom. If the set is empty, then a |
| 546 |
* single starting entry is chosen automatically among those that have the |
| 547 |
* smallest number of others that couple with it. |
| 548 |
* |
| 549 |
* <h4> Operation in parallel </h4> |
| 550 |
* |
| 551 |
* If the given DoFHandler uses a distributed triangulation (i.e., if |
| 552 |
* dof_handler.locally_owned() is not the complete index set), the |
| 553 |
* renumbering is performed on each processor's degrees of freedom |
| 554 |
* individually, without any communication between processors. In other |
| 555 |
* words, the resulting renumbering is an attempt at minimizing the bandwidth |
| 556 |
* of <i>each diagonal block of the matrix corresponding to one processor</i> |
| 557 |
* separately, without making an attempt at minimizing the bandwidth of |
| 558 |
* the global matrix. Furthermore, the renumbering reuses exactly the |
| 559 |
* same set of DoF indices that each processor used before. In other words, |
| 560 |
* if the previous numbering of DoFs on one processor used a contiguous |
| 561 |
* range of DoF indices, then so will the DoFs on that processor after |
| 562 |
* the renumbering, and they will occupy the same range. The same is true |
| 563 |
* if the previous numbering of DoFs on a processor consisted of a number |
| 564 |
* of index ranges or single indices: after renumbering, the locally owned |
| 565 |
* DoFs on that processor will use the exact same indices, just in a |
| 566 |
* different order. |
| 567 |
* |
| 568 |
* In addition, if the DoFHandler is built on a parallel triangulation, then |
| 569 |
* on every processor, the starting indices for renumbering need to be a |
| 570 |
* (possibly empty) subset of the |
| 571 |
* @ref GlossLocallyActiveDof "locally active degrees of freedom". In |
| 572 |
* general, these starting indices will be different on each processor |
| 573 |
* (unless of course you pass an empty list as is the default), |
| 574 |
* and each processor will use them as starting indices for the local |
| 575 |
* renumbering on that processor. |
| 576 |
* |
| 577 |
* The starting indices must be locally active degrees of freedom, but |
| 578 |
* the function will only renumber the locally owned subset of the |
| 579 |
* locally owned DoFs. The function accepts starting indices from the |
| 580 |
* largest set of locally active degrees of freedom because a typical |
| 581 |
* renumbering operation with this function starts with indices that |
| 582 |
* are located on the boundary -- in the case of the current function, |
| 583 |
* that would be the boundary between processor subdomains. Since the |
| 584 |
* degrees of freedom that are located on subdomain interfaces may |
| 585 |
* be owned by either one of the two processors that own the adjacent |
| 586 |
* subdomains, it is not always easy to identify starting indices that |
| 587 |
* are locally owned. On the other hand, all degrees of freedom on subdomain |
| 588 |
* interfaces are locally active, and so the function accepts them as |
| 589 |
* starting indices even though it can only renumber them on a given |
| 590 |
* processor if they are also locally owned. |
| 591 |
*/ |
| 592 |
template <int dim, int spacedim> |
| 593 |
void |
| 594 |
Cuthill_McKee(DoFHandler<dim, spacedim> &dof_handler, |
| 595 |
const bool reversed_numbering = false, |
| 596 |
const bool use_constraints = false, |
| 597 |
const std::vector<types::global_dof_index> &starting_indices = |
| 598 |
std::vector<types::global_dof_index>()); |
| 599 |
|
| 600 |
/** |
| 601 |
* Compute the renumbering vector needed by the Cuthill_McKee() function. |
| 602 |
* This function does not perform the renumbering on the DoFHandler DoFs but |
| 603 |
* only returns the renumbering vector. |
| 604 |
* |
| 605 |
* If a valid level is passed as parameter, the renumbering vector for this |
| 606 |
* grid level is returned. |
| 607 |
* See the Cuthill_McKee() function for an explanation of the other arguments. |
| 608 |
*/ |
| 609 |
template <int dim, int spacedim> |
| 610 |
void |
| 611 |
compute_Cuthill_McKee( |
| 612 |
std::vector<types::global_dof_index> &new_dof_indices, |
| 613 |
const DoFHandler<dim, spacedim> &, |
| 614 |
const bool reversed_numbering = false, |
| 615 |
const bool use_constraints = false, |
| 616 |
const std::vector<types::global_dof_index> &starting_indices = |
| 617 |
std::vector<types::global_dof_index>(), |
| 618 |
const unsigned int level = numbers::invalid_unsigned_int); |
| 619 |
|
| 620 |
/** |
| 621 |
* Renumber the degrees of freedom according to the Cuthill-McKee method, |
| 622 |
* eventually using the reverse numbering scheme, in this case for a |
| 623 |
* multigrid numbering of degrees of freedom. |
| 624 |
* |
| 625 |
* You can give a triangulation level to which this function is to be |
| 626 |
* applied. Since with a level-wise numbering there are no hanging nodes, |
| 627 |
* no constraints can be used, so the respective parameter of the previous |
| 628 |
* function is omitted. |
| 629 |
* |
| 630 |
* See the general documentation of this class for details on the different |
| 631 |
* methods. |
| 632 |
*/ |
| 633 |
template <int dim, int spacedim> |
| 634 |
void |
| 635 |
Cuthill_McKee(DoFHandler<dim, spacedim> &dof_handler, |
| 636 |
const unsigned int level, |
| 637 |
const bool reversed_numbering = false, |
| 638 |
const std::vector<types::global_dof_index> &starting_indices = |
| 639 |
std::vector<types::global_dof_index>()); |
| 640 |
|
| 641 |
/** |
| 642 |
* @name Component-wise numberings |
| 643 |
* @{ |
| 644 |
*/ |
| 645 |
|
| 646 |
/** |
| 647 |
* Sort the degrees of freedom by vector component. The numbering within |
| 648 |
* each component is not touched, so a degree of freedom with index $i$, |
| 649 |
* belonging to some component, and another degree of freedom with index $j$ |
| 650 |
* belonging to the same component will be assigned new indices $n(i)$ and |
| 651 |
* $n(j)$ with $n(i)<n(j)$ if $i<j$ and $n(i)>n(j)$ if $i>j$. |
| 652 |
* |
| 653 |
* You can specify that the components are ordered in a different way than |
| 654 |
* suggested by the FESystem object you use. To this end, set up the vector |
| 655 |
* @p target_component such that the entry at index @p i denotes the number |
| 656 |
* of the target component for dofs with component @p i in the FESystem. |
| 657 |
* Naming the same target component more than once is possible and results |
| 658 |
* in a blocking of several components into one. This is discussed in |
| 659 |
* step-22. If you omit this argument, the same order as given by the finite |
| 660 |
* element is used. |
| 661 |
* |
| 662 |
* If one of the base finite elements from which the global finite element |
| 663 |
* under consideration here, is a non-primitive one, i.e. its shape |
| 664 |
* functions have more than one non-zero component, then it is not possible |
| 665 |
* to associate these degrees of freedom with a single vector component. In |
| 666 |
* this case, they are associated with the first vector component to which |
| 667 |
* they belong. |
| 668 |
* |
| 669 |
* For finite elements with only one component, or a single non-primitive |
| 670 |
* base element, this function is the identity operation. |
| 671 |
*/ |
| 672 |
template <int dim, int spacedim> |
| 673 |
void |
| 674 |
component_wise(DoFHandler<dim, spacedim> &dof_handler, |
| 675 |
const std::vector<unsigned int> &target_component = |
| 676 |
std::vector<unsigned int>()); |
| 677 |
|
| 678 |
|
| 679 |
/** |
| 680 |
* Sort the degrees of freedom by component. It does the same thing as the |
| 681 |
* above function, only that it does this for one single level of a |
| 682 |
* multilevel discretization. The non-multigrid part of the DoFHandler |
| 683 |
* is not touched. |
| 684 |
*/ |
| 685 |
template <int dim, int spacedim> |
| 686 |
void |
| 687 |
component_wise(DoFHandler<dim, spacedim> &dof_handler, |
| 688 |
const unsigned int level, |
| 689 |
const std::vector<unsigned int> &target_component = |
| 690 |
std::vector<unsigned int>()); |
| 691 |
|
| 692 |
/** |
| 693 |
* Compute the renumbering vector needed by the component_wise() functions. |
| 694 |
* Does not perform the renumbering on the DoFHandler dofs but returns the |
| 695 |
* renumbering vector. |
| 696 |
*/ |
| 697 |
template <int dim, int spacedim, typename CellIterator> |
| 698 |
types::global_dof_index |
| 699 |
compute_component_wise(std::vector<types::global_dof_index> &new_dof_indices, |
| 700 |
const CellIterator &start, |
| 701 |
const std_cxx20::type_identity_t<CellIterator> &end, |
| 702 |
const std::vector<unsigned int> &target_component, |
| 703 |
const bool is_level_operation); |
| 704 |
|
| 705 |
/** |
| 706 |
* @} |
| 707 |
*/ |
| 708 |
|
| 709 |
/** |
| 710 |
* @name Block-wise numberings |
| 711 |
* @{ |
| 712 |
*/ |
| 713 |
|
| 714 |
/** |
| 715 |
* Sort the degrees of freedom by vector block. The numbering within each |
| 716 |
* block is not touched, so a degree of freedom with index $i$, belonging to |
| 717 |
* some block, and another degree of freedom with index $j$ belonging to the |
| 718 |
* same block will be assigned new indices $n(i)$ and $n(j)$ with |
| 719 |
* $n(i)<n(j)$ if $i<j$ and $n(i)>n(j)$ if $i>j$. |
| 720 |
* |
| 721 |
* @note This function only succeeds if each of the elements in the |
| 722 |
* hp::FECollection attached to the DoFHandler argument has exactly the |
| 723 |
* same number of blocks (see |
| 724 |
* @ref GlossBlock "the glossary" |
| 725 |
* for more information). Note that this is not always given: while the |
| 726 |
* hp::FECollection class ensures that all of its elements have the same |
| 727 |
* number of vector components, they need not have the same number of |
| 728 |
* blocks. At the same time, this function here needs to match individual |
| 729 |
* blocks across elements and therefore requires that elements have the same |
| 730 |
* number of blocks and that subsequent blocks in one element have the same |
| 731 |
* meaning as in another element. |
| 732 |
*/ |
| 733 |
template <int dim, int spacedim> |
| 734 |
void |
| 735 |
block_wise(DoFHandler<dim, spacedim> &dof_handler); |
| 736 |
|
| 737 |
/** |
| 738 |
* Sort the degrees of freedom by vector block. It does the same thing as |
| 739 |
* the above function, only that it does this for one single level of a |
| 740 |
* multilevel discretization. The non-multigrid part of the DoFHandler |
| 741 |
* is not touched. |
| 742 |
*/ |
| 743 |
template <int dim, int spacedim> |
| 744 |
void |
| 745 |
block_wise(DoFHandler<dim, spacedim> &dof_handler, const unsigned int level); |
| 746 |
|
| 747 |
/** |
| 748 |
* Compute the renumbering vector needed by the block_wise() functions. |
| 749 |
* Does not perform the renumbering on the DoFHandler dofs but returns the |
| 750 |
* renumbering vector. |
| 751 |
*/ |
| 752 |
template <int dim, int spacedim, class IteratorType, class EndIteratorType> |
| 753 |
types::global_dof_index |
| 754 |
compute_block_wise(std::vector<types::global_dof_index> &new_dof_indices, |
| 755 |
const IteratorType &start, |
| 756 |
const EndIteratorType &end, |
| 757 |
const bool is_level_operation); |
| 758 |
|
| 759 |
/** |
| 760 |
* @} |
| 761 |
*/ |
| 762 |
|
| 763 |
/** |
| 764 |
* @name Various cell-wise numberings |
| 765 |
* @{ |
| 766 |
*/ |
| 767 |
|
| 768 |
/** |
| 769 |
* Renumber the degrees cell by cell by traversing the cells in |
| 770 |
* @ref GlossZOrder "Z order". |
| 771 |
* |
| 772 |
* There are two reasons to use this function: |
| 773 |
* - It produces a predictable ordering of degrees of freedom |
| 774 |
* that is independent of how exactly you arrived at a mesh. |
| 775 |
* In particular, in general the order of cells of a mesh |
| 776 |
* depends on the order in which cells were marked for |
| 777 |
* refinement and coarsening during the refinement cycles |
| 778 |
* the mesh has undergone. On the other hand, the z-order |
| 779 |
* of cells is independent of the mesh's history, and so yields a |
| 780 |
* predictable DoF numbering. |
| 781 |
* - For meshes based on parallel::distributed::Triangulation, |
| 782 |
* the |
| 783 |
* @ref GlossLocallyOwnedCell "locally owned cells" |
| 784 |
* of |
| 785 |
* each MPI process are contiguous in Z order. That means that |
| 786 |
* numbering degrees of freedom by visiting cells in Z order yields |
| 787 |
* @ref GlossLocallyOwnedDof "locally owned DoF indices" |
| 788 |
* that consist |
| 789 |
* of contiguous ranges for each process. This is also true for the |
| 790 |
* default ordering of DoFs on such triangulations, but the default |
| 791 |
* ordering creates an enumeration that also depends on how many |
| 792 |
* processors participate in the mesh, whereas the one generated |
| 793 |
* by this function enumerates the degrees of freedom on a particular |
| 794 |
* cell with indices that will be the same regardless of how many |
| 795 |
* processes the mesh is split up between. |
| 796 |
* |
| 797 |
* For meshes based on parallel::shared::Triangulation, the situation is |
| 798 |
* more complex. Here, the set of locally owned cells is determined by |
| 799 |
* a partitioning algorithm (selected by passing an object of type |
| 800 |
* parallel::shared::Triangulation::Settings to the constructor of the |
| 801 |
* triangulation), and in general these partitioning algorithms may |
| 802 |
* assign cells to |
| 803 |
* @ref GlossSubdomainId "subdomains" |
| 804 |
* based on |
| 805 |
* decisions that may have nothing to do with the Z order. (Though it |
| 806 |
* is possible to select these flags in a way so that partitioning |
| 807 |
* uses the Z order.) As a consequence, the cells of one subdomain |
| 808 |
* are not contiguous in Z order, and if one renumbered degrees of freedom |
| 809 |
* based on the Z order of cells, one would generally end up with DoF |
| 810 |
* indices that on each processor do not form a contiguous range. |
| 811 |
* This is often inconvenient (for example, because PETSc cannot store |
| 812 |
* vectors and matrices for which the locally owned set of indices |
| 813 |
* is not contiguous), and consequently this function uses the following |
| 814 |
* algorithm for parallel::shared::Triangulation objects: |
| 815 |
* - It determines how many degrees of freedom each processor owns. |
| 816 |
* This is an invariant under renumbering, and consequently we can |
| 817 |
* use how many DoFs each processor owns at the beginning of the current |
| 818 |
* function. Let us call this number $n_P$ for processor $P$. |
| 819 |
* - It determines for each processor a contiguous range of new |
| 820 |
* DoF indices $[b_P,e_P)$ so that $e_P-b_P=n_P$, $b_0=0$, and |
| 821 |
* $b_P=e_{P-1}$. |
| 822 |
* - It traverses the <i>locally owned cells</i> in Z order and |
| 823 |
* renumbers the locally owned degrees of freedom on these cells |
| 824 |
* so that the new numbers fit within the interval $[b_P,e_P)$. |
| 825 |
* In other words, the <i>locally owned degrees of freedom</i> on each |
| 826 |
* processor are sorted according to the Z order of the locally |
| 827 |
* owned cells they are on, but this property may not hold globally, |
| 828 |
* across cells. This is because the partitioning algorithm may have |
| 829 |
* decided that, for example, processor 0 owns a cell that comes |
| 830 |
* <i>later</i> in Z order than one of the cells assigned to processor 1. |
| 831 |
* On the other hand, the algorithm described above assigns the |
| 832 |
* degrees of freedom on this cell <i>earlier</i> indices than |
| 833 |
* all of the indices owned by processor 1. |
| 834 |
* |
| 835 |
* @note This function generates an ordering that is independent of the previous |
| 836 |
* numbering of degrees of freedom. In other words, any information that may |
| 837 |
* have been produced by a previous call to a renumbering function is |
| 838 |
* ignored. |
| 839 |
*/ |
| 840 |
template <int dim, int spacedim> |
| 841 |
void |
| 842 |
hierarchical(DoFHandler<dim, spacedim> &dof_handler); |
| 843 |
|
| 844 |
/** |
| 845 |
* Renumber degrees of freedom by cell. The function takes a vector of cell |
| 846 |
* iterators (which needs to list <i>all</i> locally owned active cells of the |
| 847 |
* DoF handler objects) and will give degrees of freedom new indices based on |
| 848 |
* where in the given list of cells the cell is on which the degree of freedom |
| 849 |
* is located. Degrees of freedom that exist at the interface between two or |
| 850 |
* more cells will be numbered when they are encountered first. |
| 851 |
* |
| 852 |
* Degrees of freedom that are encountered first on the same cell retain |
| 853 |
* their original ordering before the renumbering step. |
| 854 |
* |
| 855 |
* @param[in,out] dof_handler The DoFHandler whose degrees of freedom are to |
| 856 |
* be renumbered. |
| 857 |
* @param[in] cell_order A vector that contains the order of the cells that |
| 858 |
* defines the order in which degrees of freedom should be renumbered. |
| 859 |
* |
| 860 |
* @pre for serial triangulation @p cell_order must have size |
| 861 |
* <code>dof_handler.get_triangulation().n_active_cells()</code>, whereas |
| 862 |
* in case of parallel triangulation its size should be |
| 863 |
* parallel::TriangulationBase::n_locally_owned_active_cells(). Every active |
| 864 |
* cell |
| 865 |
* iterator of that triangulation needs to be present in @p cell_order exactly |
| 866 |
* once. |
| 867 |
*/ |
| 868 |
template <int dim, int spacedim> |
| 869 |
void |
| 870 |
cell_wise( |
| 871 |
DoFHandler<dim, spacedim> &dof_handler, |
| 872 |
const std::vector<typename DoFHandler<dim, spacedim>::active_cell_iterator> |
| 873 |
&cell_order); |
| 874 |
|
| 875 |
/** |
| 876 |
* Compute a renumbering of degrees of freedom by cell. The function takes a |
| 877 |
* vector of cell iterators (which needs to list <i>all</i> locally owned |
| 878 |
* active cells of the DoF handler objects) and will give degrees of freedom |
| 879 |
* new indices based on where in the given list of cells the cell is on which |
| 880 |
* the degree of freedom is located. Degrees of freedom that exist at the |
| 881 |
* interface between two or more cells will be numbered when they are |
| 882 |
* encountered first. |
| 883 |
* |
| 884 |
* Degrees of freedom that are encountered first on the same cell retain |
| 885 |
* their original ordering before the renumbering step. |
| 886 |
* |
| 887 |
* @param[out] renumbering A vector of length |
| 888 |
* <code>dof_handler.n_locally_owned_dofs()</code> that contains for each |
| 889 |
* degree of freedom (in their current numbering) their future DoF index. This |
| 890 |
* vector therefore presents a (very particular) <i>permutation</i> of the |
| 891 |
* current DoF indices. |
| 892 |
* @param[out] inverse_renumbering The reverse of the permutation returned |
| 893 |
* in the previous argument. In case of parallel::TriangulationBase the |
| 894 |
* inverse is within locally owned DoFs. |
| 895 |
* @param[in] dof_handler The DoFHandler whose degrees of freedom are to be |
| 896 |
* renumbered. |
| 897 |
* @param[in] cell_order A vector that contains the order of the cells that |
| 898 |
* defines the order in which degrees of freedom should be renumbered. |
| 899 |
* |
| 900 |
* @pre for serial triangulation @p cell_order must have size |
| 901 |
* <code>dof_handler.get_triangulation().n_active_cells()</code>, whereas |
| 902 |
* in case of parallel triangulation its size should be |
| 903 |
* parallel::TriangulationBase::n_locally_owned_active_cells(). Every active |
| 904 |
* cell iterator of that triangulation needs to be present in @p |
| 905 |
* cell_order exactly once. @post For each @p i between zero and |
| 906 |
* <code>dof_handler.n_locally_owned_dofs()</code>, the condition |
| 907 |
* <code>renumbering[inverse_renumbering[i]] == |
| 908 |
* dof_handler.locally_owned_dofs().nth_index_in_set(i)</code> will hold. |
| 909 |
*/ |
| 910 |
template <int dim, int spacedim> |
| 911 |
void |
| 912 |
compute_cell_wise( |
| 913 |
std::vector<types::global_dof_index> &renumbering, |
| 914 |
std::vector<types::global_dof_index> &inverse_renumbering, |
| 915 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 916 |
const std::vector<typename DoFHandler<dim, spacedim>::active_cell_iterator> |
| 917 |
&cell_order); |
| 918 |
|
| 919 |
/** |
| 920 |
* Like the other cell_wise() function, but for one level of a multilevel |
| 921 |
* enumeration of degrees of freedom. |
| 922 |
*/ |
| 923 |
template <int dim, int spacedim> |
| 924 |
void |
| 925 |
cell_wise( |
| 926 |
DoFHandler<dim, spacedim> &dof_handler, |
| 927 |
const unsigned int level, |
| 928 |
const std::vector<typename DoFHandler<dim, spacedim>::level_cell_iterator> |
| 929 |
&cell_order); |
| 930 |
|
| 931 |
/** |
| 932 |
* Like the other compute_cell_wise() function, but for one level of a |
| 933 |
* multilevel enumeration of degrees of freedom. |
| 934 |
*/ |
| 935 |
template <int dim, int spacedim> |
| 936 |
void |
| 937 |
compute_cell_wise( |
| 938 |
std::vector<types::global_dof_index> &renumbering, |
| 939 |
std::vector<types::global_dof_index> &inverse_renumbering, |
| 940 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 941 |
const unsigned int level, |
| 942 |
const std::vector<typename DoFHandler<dim, spacedim>::level_cell_iterator> |
| 943 |
&cell_order); |
| 944 |
|
| 945 |
/** |
| 946 |
* @} |
| 947 |
*/ |
| 948 |
|
| 949 |
/** |
| 950 |
* @name Directional numberings |
| 951 |
* @{ |
| 952 |
*/ |
| 953 |
|
| 954 |
/** |
| 955 |
* Downstream numbering with respect to a constant flow direction. If the |
| 956 |
* additional argument @p dof_wise_renumbering is set to @p false, the |
| 957 |
* numbering is performed cell-wise, otherwise it is performed based on the |
| 958 |
* location of the support points. |
| 959 |
* |
| 960 |
* The cells are sorted such that the centers of cells numbered higher are |
| 961 |
* further |
| 962 |
* downstream with respect to the constant vector @p direction than the |
| 963 |
* centers of cells numbered lower. Even if this yields a downstream numbering |
| 964 |
* with respect to the flux on the edges for fairly general grids, this might |
| 965 |
* not be guaranteed for all meshes. |
| 966 |
* |
| 967 |
* If the @p dof_wise_renumbering argument is set to @p false, this function |
| 968 |
* produces a downstream ordering of the mesh cells and calls cell_wise(). |
| 969 |
* Therefore, the output only makes sense for Discontinuous Galerkin Finite |
| 970 |
* Elements (all degrees of freedom have to be associated with the interior |
| 971 |
* of the cell in that case) in that case. |
| 972 |
* |
| 973 |
* If @p dof_wise_renumbering is set to @p true, the degrees of freedom are |
| 974 |
* renumbered based on the support point location of the individual degrees |
| 975 |
* of freedom (obviously, the finite element needs to define support points |
| 976 |
* for this to work). The numbering of points with the same position in |
| 977 |
* downstream location (e.g. those parallel to the flow direction, or |
| 978 |
* several dofs within a FESystem) will be unaffected. |
| 979 |
*/ |
| 980 |
template <int dim, int spacedim> |
| 981 |
void |
| 982 |
downstream(DoFHandler<dim, spacedim> &dof_handler, |
| 983 |
const Tensor<1, spacedim> &direction, |
| 984 |
const bool dof_wise_renumbering = false); |
| 985 |
|
| 986 |
|
| 987 |
/** |
| 988 |
* Cell-wise downstream numbering with respect to a constant flow direction |
| 989 |
* on one level of a multigrid hierarchy. See the other function with the same |
| 990 |
* name. |
| 991 |
*/ |
| 992 |
template <int dim, int spacedim> |
| 993 |
void |
| 994 |
downstream(DoFHandler<dim, spacedim> &dof_handler, |
| 995 |
const unsigned int level, |
| 996 |
const Tensor<1, spacedim> &direction, |
| 997 |
const bool dof_wise_renumbering = false); |
| 998 |
|
| 999 |
/** |
| 1000 |
* Compute the set of renumbering indices needed by the downstream() function. |
| 1001 |
* Does not perform the renumbering on the DoFHandler dofs but returns the |
| 1002 |
* renumbering vector. |
| 1003 |
*/ |
| 1004 |
template <int dim, int spacedim> |
| 1005 |
void |
| 1006 |
compute_downstream(std::vector<types::global_dof_index> &new_dof_indices, |
| 1007 |
std::vector<types::global_dof_index> &reverse, |
| 1008 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 1009 |
const Tensor<1, spacedim> &direction, |
| 1010 |
const bool dof_wise_renumbering); |
| 1011 |
|
| 1012 |
/** |
| 1013 |
* Compute the set of renumbering indices needed by the downstream() function. |
| 1014 |
* Does not perform the renumbering on the DoFHandler dofs but returns the |
| 1015 |
* renumbering vector. |
| 1016 |
*/ |
| 1017 |
template <int dim, int spacedim> |
| 1018 |
void |
| 1019 |
compute_downstream(std::vector<types::global_dof_index> &new_dof_indices, |
| 1020 |
std::vector<types::global_dof_index> &reverse, |
| 1021 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 1022 |
const unsigned int level, |
| 1023 |
const Tensor<1, spacedim> &direction, |
| 1024 |
const bool dof_wise_renumbering); |
| 1025 |
|
| 1026 |
/** |
| 1027 |
* Cell-wise clockwise numbering. |
| 1028 |
* |
| 1029 |
* This function produces a (counter)clockwise ordering of the mesh cells |
| 1030 |
* with respect to the hub @p center and calls cell_wise(). Therefore, it |
| 1031 |
* only works with Discontinuous Galerkin Finite Elements, i.e. all degrees |
| 1032 |
* of freedom have to be associated with the interior of the cell. |
| 1033 |
*/ |
| 1034 |
template <int dim, int spacedim> |
| 1035 |
void |
| 1036 |
clockwise_dg(DoFHandler<dim, spacedim> &dof_handler, |
| 1037 |
const Point<spacedim> ¢er, |
| 1038 |
const bool counter = false); |
| 1039 |
|
| 1040 |
/** |
| 1041 |
* Cell-wise clockwise numbering on one level of a multigrid |
| 1042 |
* hierarchy. See the other function with the same name. |
| 1043 |
*/ |
| 1044 |
template <int dim, int spacedim> |
| 1045 |
void |
| 1046 |
clockwise_dg(DoFHandler<dim, spacedim> &dof_handler, |
| 1047 |
const unsigned int level, |
| 1048 |
const Point<spacedim> ¢er, |
| 1049 |
const bool counter = false); |
| 1050 |
|
| 1051 |
/** |
| 1052 |
* Compute the renumbering vector needed by the clockwise_dg() functions. |
| 1053 |
* Does not perform the renumbering on the DoFHandler dofs but returns the |
| 1054 |
* renumbering vector. |
| 1055 |
*/ |
| 1056 |
template <int dim, int spacedim> |
| 1057 |
void |
| 1058 |
compute_clockwise_dg(std::vector<types::global_dof_index> &new_dof_indices, |
| 1059 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 1060 |
const Point<spacedim> ¢er, |
| 1061 |
const bool counter); |
| 1062 |
|
| 1063 |
/** |
| 1064 |
* @} |
| 1065 |
*/ |
| 1066 |
|
| 1067 |
/** |
| 1068 |
* @name Selective and random numberings |
| 1069 |
* @{ |
| 1070 |
*/ |
| 1071 |
|
| 1072 |
/** |
| 1073 |
* Sort those degrees of freedom which are tagged with @p true in the @p |
| 1074 |
* selected_dofs array to the back of the DoF numbers. The sorting is |
| 1075 |
* stable, i.e. the relative order within the tagged degrees of freedom is |
| 1076 |
* preserved, as is the relative order within the untagged ones. |
| 1077 |
* |
| 1078 |
* @pre The @p selected_dofs array must have as many elements as the @p |
| 1079 |
* dof_handler has degrees of freedom. |
| 1080 |
*/ |
| 1081 |
template <int dim, int spacedim> |
| 1082 |
void |
| 1083 |
sort_selected_dofs_back(DoFHandler<dim, spacedim> &dof_handler, |
| 1084 |
const std::vector<bool> &selected_dofs); |
| 1085 |
|
| 1086 |
/** |
| 1087 |
* Sort those degrees of freedom which are tagged with @p true in the @p |
| 1088 |
* selected_dofs array on the level @p level to the back of the DoF numbers. |
| 1089 |
* The sorting is stable, i.e. the relative order within the tagged degrees |
| 1090 |
* of freedom is preserved, as is the relative order within the untagged |
| 1091 |
* ones. |
| 1092 |
* |
| 1093 |
* @pre The @p selected_dofs array must have as many elements as the @p |
| 1094 |
* dof_handler has degrees of freedom on the given level. |
| 1095 |
*/ |
| 1096 |
template <int dim, int spacedim> |
| 1097 |
void |
| 1098 |
sort_selected_dofs_back(DoFHandler<dim, spacedim> &dof_handler, |
| 1099 |
const std::vector<bool> &selected_dofs, |
| 1100 |
const unsigned int level); |
| 1101 |
|
| 1102 |
/** |
| 1103 |
* Compute the renumbering vector needed by the sort_selected_dofs_back() |
| 1104 |
* function. Does not perform the renumbering on the DoFHandler dofs but |
| 1105 |
* returns the renumbering vector. |
| 1106 |
* |
| 1107 |
* @pre The @p selected_dofs array must have as many elements as the @p |
| 1108 |
* dof_handler has degrees of freedom. |
| 1109 |
*/ |
| 1110 |
template <int dim, int spacedim> |
| 1111 |
void |
| 1112 |
compute_sort_selected_dofs_back( |
| 1113 |
std::vector<types::global_dof_index> &new_dof_indices, |
| 1114 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 1115 |
const std::vector<bool> &selected_dofs); |
| 1116 |
|
| 1117 |
/** |
| 1118 |
* This function computes the renumbering vector on each level needed by the |
| 1119 |
* sort_selected_dofs_back() function. Does not perform the renumbering on |
| 1120 |
* the DoFHandler dofs but only computes the renumbering and returns the |
| 1121 |
* renumbering vector. |
| 1122 |
* |
| 1123 |
* @pre The @p selected_dofs array must have as many elements as the @p |
| 1124 |
* dof_handler has degrees of freedom on the given level. |
| 1125 |
*/ |
| 1126 |
template <int dim, int spacedim> |
| 1127 |
void |
| 1128 |
compute_sort_selected_dofs_back( |
| 1129 |
std::vector<types::global_dof_index> &new_dof_indices, |
| 1130 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 1131 |
const std::vector<bool> &selected_dofs, |
| 1132 |
const unsigned int level); |
| 1133 |
|
| 1134 |
/** |
| 1135 |
* Renumber the degrees of freedom in a random way. The result of this |
| 1136 |
* function is repeatable in that two runs of the same program will yield |
| 1137 |
* the same result. This is achieved by creating a new random number |
| 1138 |
* generator with a fixed seed every time this function is entered. In |
| 1139 |
* particular, the function therefore does not rely on an external random |
| 1140 |
* number generator for which it would matter how often it has been called |
| 1141 |
* before this function (or, for that matter, whether other threads running |
| 1142 |
* concurrently to this function also draw random numbers). |
| 1143 |
*/ |
| 1144 |
template <int dim, int spacedim> |
| 1145 |
void |
| 1146 |
random(DoFHandler<dim, spacedim> &dof_handler); |
| 1147 |
|
| 1148 |
/** |
| 1149 |
* Renumber the degrees of freedom in a random way. It does the same thing as |
| 1150 |
* the above function, only that it does this for one single level of a |
| 1151 |
* multilevel discretization. The non-multigrid part of the DoFHandler |
| 1152 |
* is not touched. |
| 1153 |
*/ |
| 1154 |
template <int dim, int spacedim> |
| 1155 |
void |
| 1156 |
random(DoFHandler<dim, spacedim> &dof_handler, const unsigned int level); |
| 1157 |
|
| 1158 |
/** |
| 1159 |
* Compute the renumbering vector needed by the random() function. See |
| 1160 |
* there for more information on the computed random renumbering. |
| 1161 |
* |
| 1162 |
* This function does not perform the renumbering on the DoFHandler dofs but |
| 1163 |
* returns the renumbering vector. |
| 1164 |
*/ |
| 1165 |
template <int dim, int spacedim> |
| 1166 |
void |
| 1167 |
compute_random(std::vector<types::global_dof_index> &new_dof_indices, |
| 1168 |
const DoFHandler<dim, spacedim> &dof_handler); |
| 1169 |
|
| 1170 |
/** |
| 1171 |
* Compute the renumbering vector needed by the random() function. Same |
| 1172 |
* as the above function but for a single level of a multilevel |
| 1173 |
* discretization. |
| 1174 |
*/ |
| 1175 |
template <int dim, int spacedim> |
| 1176 |
void |
| 1177 |
compute_random(std::vector<types::global_dof_index> &new_dof_indices, |
| 1178 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 1179 |
const unsigned int level); |
| 1180 |
|
| 1181 |
/** |
| 1182 |
* @} |
| 1183 |
*/ |
| 1184 |
|
| 1185 |
/** |
| 1186 |
* @name Numberings based on cell attributes |
| 1187 |
* @{ |
| 1188 |
*/ |
| 1189 |
|
| 1190 |
/** |
| 1191 |
* Renumber the degrees of freedom such that they are associated with the |
| 1192 |
* subdomain id of the cells they are living on, i.e. first all degrees of |
| 1193 |
* freedom that belong to cells with subdomain zero, then all with subdomain |
| 1194 |
* one, etc. This is useful when doing parallel computations with a standard |
| 1195 |
* Triangulation after assigning subdomain ids using a partitioner (see the |
| 1196 |
* GridTools::partition_triangulation function for this). Calling this |
| 1197 |
* function is unnecessary when using a parallel::shared::Triangulation or |
| 1198 |
* parallel::distributed::Triangulation, as the degrees of freedom are |
| 1199 |
* already enumerated according to the MPI process id. Therefore, if the |
| 1200 |
* underlying triangulation is of this type then an error will be thrown. |
| 1201 |
* |
| 1202 |
* Note that degrees of freedom associated with faces, edges, and vertices |
| 1203 |
* may be associated with multiple subdomains if they are sitting on |
| 1204 |
* partition boundaries. It would therefore be undefined with which |
| 1205 |
* subdomain they have to be associated. For this, we use what we get from |
| 1206 |
* the DoFTools::get_subdomain_association function. |
| 1207 |
* |
| 1208 |
* The algorithm is stable, i.e. if two dofs i,j have <tt>i<j</tt> and |
| 1209 |
* belong to the same subdomain, then they will be in this order also after |
| 1210 |
* reordering. |
| 1211 |
*/ |
| 1212 |
template <int dim, int spacedim> |
| 1213 |
void |
| 1214 |
subdomain_wise(DoFHandler<dim, spacedim> &dof_handler); |
| 1215 |
|
| 1216 |
/** |
| 1217 |
* Compute the renumbering vector needed by the subdomain_wise() function. |
| 1218 |
* Does not perform the renumbering on the @p DoFHandler dofs but returns |
| 1219 |
* the renumbering vector. |
| 1220 |
*/ |
| 1221 |
template <int dim, int spacedim> |
| 1222 |
void |
| 1223 |
compute_subdomain_wise(std::vector<types::global_dof_index> &new_dof_indices, |
| 1224 |
const DoFHandler<dim, spacedim> &dof_handler); |
| 1225 |
|
| 1226 |
/** |
| 1227 |
* @} |
| 1228 |
*/ |
| 1229 |
|
| 1230 |
/** |
| 1231 |
* @name Numberings based on properties of the finite element space |
| 1232 |
* @{ |
| 1233 |
*/ |
| 1234 |
|
| 1235 |
/** |
| 1236 |
* Stably sort DoFs first by component and second by location of their support |
| 1237 |
* points, so that DoFs with the same support point are listed consecutively |
| 1238 |
* in the component order. |
| 1239 |
* |
| 1240 |
* The primary use of this ordering is that it enables one to interpret a |
| 1241 |
* vector of FE coefficients as a vector of tensors. For example, suppose `X` |
| 1242 |
* is a vector containing coordinates (i.e., the sort of vector one would use |
| 1243 |
* with MappingFEField) and `U` is a vector containing velocities in 2d. Then |
| 1244 |
* the `k`th support point is mapped to `{X[2*k], X[2*k + 1]}` and the |
| 1245 |
* velocity there is `{U[2*k], U[2*k + 1]}`. Hence, with this reordering, one |
| 1246 |
* can read solution data at each support point without additional indexing. |
| 1247 |
* This is useful for, e.g., passing vectors of FE coefficients to external |
| 1248 |
* libraries which expect nodal data in this format. |
| 1249 |
* |
| 1250 |
* @warning This function only supports finite elements which have the same |
| 1251 |
* number of DoFs in each component. This is checked with an assertion. |
| 1252 |
* |
| 1253 |
* @note This renumbering assumes that the base elements of each vector-valued |
| 1254 |
* element in @p dof_handler are numbered in the way FESystem currently |
| 1255 |
* distributes DoFs: i.e., for a given support point, the global dof indices |
| 1256 |
* for component i should be less than the global dof indices for component i |
| 1257 |
* + 1. Due to various technical complications (like DoF unification in |
| 1258 |
* hp-mode) this assumption needs to be satisfied for this function to work in |
| 1259 |
* all relevant cases. |
| 1260 |
*/ |
| 1261 |
template <int dim, int spacedim> |
| 1262 |
void |
| 1263 |
support_point_wise(DoFHandler<dim, spacedim> &dof_handler); |
| 1264 |
|
| 1265 |
/** |
| 1266 |
* Compute the renumbering vector needed by the support_point_wise() function. |
| 1267 |
* Does not perform the renumbering on the @p DoFHandler dofs but returns the |
| 1268 |
* renumbering vector. |
| 1269 |
*/ |
| 1270 |
template <int dim, int spacedim> |
| 1271 |
void |
| 1272 |
compute_support_point_wise( |
| 1273 |
std::vector<types::global_dof_index> &new_dof_indices, |
| 1274 |
const DoFHandler<dim, spacedim> &dof_handler); |
| 1275 |
|
| 1276 |
/** |
| 1277 |
* Reorder the degrees of freedom in lexicographic order of support points. |
| 1278 |
* The tolerance is used to determine whether two support points are equal. |
| 1279 |
* |
| 1280 |
* This is particularly useful for finite element spaces that are defined on |
| 1281 |
* tensor product grids, such as the ones generated by |
| 1282 |
* GridGenerator::hyper_rectangle() or GridGenerator::hyper_cube() or |
| 1283 |
* their subdivided variants. |
| 1284 |
* With this ordering certain higher-dimension finite element matrices can be |
| 1285 |
* expressed as Kronecker products of lower-dimensional matrices. |
| 1286 |
* |
| 1287 |
* @warning parallel::distributed::Triangulation objects are not supported. |
| 1288 |
* The finite element must have support points. |
| 1289 |
*/ |
| 1290 |
template <int dim> |
| 1291 |
void |
| 1292 |
lexicographic(DoFHandler<dim> &dof_handler, const double tolerance = 1e-12); |
| 1293 |
|
| 1294 |
/** |
| 1295 |
* Compute the renumbering vector needed by the lexicographic() function. |
| 1296 |
* Does not perform the renumbering on the @p DoFHandler dofs but returns the |
| 1297 |
* renumbering vector. |
| 1298 |
* The tolerance is treated as an absolute tolerance for comparing support |
| 1299 |
* point coordinates. To use a relative tolerance, multiply a relative value |
| 1300 |
* by dof_handler.begin(0)->diameter() or a similar characteristic length. |
| 1301 |
*/ |
| 1302 |
template <int dim> |
| 1303 |
void |
| 1304 |
compute_lexicographic(std::vector<types::global_dof_index> &new_dof_indices, |
| 1305 |
const DoFHandler<dim> &handler, |
| 1306 |
const double tolerance = 1e-12); |
| 1307 |
|
| 1308 |
/** |
| 1309 |
* @} |
| 1310 |
*/ |
| 1311 |
|
| 1312 |
/** |
| 1313 |
* @name Numberings for better performance with the MatrixFree infrastructure |
| 1314 |
* @{ |
| 1315 |
*/ |
| 1316 |
|
| 1317 |
/** |
| 1318 |
* Sort DoFs by their appearance in matrix-free loops in order to increase |
| 1319 |
* data locality when accessing solution vectors with shared DoFs. More |
| 1320 |
* specifically, this renumbering strategy will group DoFs touched only on a |
| 1321 |
* single group of cells (as traversed by a MatrixFree::cell_loop()) nearby, |
| 1322 |
* whereas DoFs touched far apart through the loop over cells are grouped |
| 1323 |
* separately. This approach allows to interleave operations before and |
| 1324 |
* after the cell operations while data is still hot in caches for most |
| 1325 |
* parts of the vector. Since DoFs subject to ghost exchange will also |
| 1326 |
* have far reach, they will also be grouped separately. Currently, this |
| 1327 |
* function only works for finite elements of type FE_Q as well as systems of |
| 1328 |
* a single FE_Q element. |
| 1329 |
* |
| 1330 |
* This function needs to be given a `matrix_free` object with the indices |
| 1331 |
* set up, in order to determine the order in which cells are passed |
| 1332 |
* through. Note that it is necessary to set up constraints and MatrixFree |
| 1333 |
* again after renumbering, so there is no need to set up the mapping |
| 1334 |
* information for this point, see |
| 1335 |
* MatrixFree::AdditionalData::initialize_mapping. As MatrixFree allows to |
| 1336 |
* be set up with multiple DoFHandler objects, the DoFHandler additionally |
| 1337 |
* passed in is used to identify the correct DoFHandler. There is also an |
| 1338 |
* alternative renumbering function with the same name that only takes the |
| 1339 |
* MatrixFree::AdditionalData to identify the indices; which that function |
| 1340 |
* is to be preferred when only a single DoFHandler is involved, cases with |
| 1341 |
* multiple DoFHandler objects in MatrixFree need to choose this function, |
| 1342 |
* as the order of how cells get passed through depends on the indices on |
| 1343 |
* all cells. |
| 1344 |
* |
| 1345 |
* @note This functions can compute a new order both on the active cells and |
| 1346 |
* the level cells, using information in the MatrixFree::get_mg_level() |
| 1347 |
* function. |
| 1348 |
*/ |
| 1349 |
template <int dim, |
| 1350 |
int spacedim, |
| 1351 |
typename Number, |
| 1352 |
typename VectorizedArrayType> |
| 1353 |
void |
| 1354 |
matrix_free_data_locality( |
| 1355 |
DoFHandler<dim, spacedim> &dof_handler, |
| 1356 |
const MatrixFree<dim, Number, VectorizedArrayType> &matrix_free); |
| 1357 |
|
| 1358 |
/** |
| 1359 |
* Same function as the one above, but taking a MatrixFree::AdditionalData |
| 1360 |
* object instead. This allows for easier and cheaper computation of the new |
| 1361 |
* numbering in case only a single DoFHandler will be present in the final |
| 1362 |
* MatrixFree object. In order to determine the relevant constraints of the |
| 1363 |
* matrix-free loop, the AffineConstraints objects also passed to MatrixFree |
| 1364 |
* needs to be provided. Furthermore, it is possible to set a multigrid |
| 1365 |
* level by MatrixFree::AdditionalData::mg_level. |
| 1366 |
*/ |
| 1367 |
template <int dim, int spacedim, typename Number, typename AdditionalDataType> |
| 1368 |
void |
| 1369 |
matrix_free_data_locality( |
| 1370 |
DoFHandler<dim, spacedim> &dof_handler, |
| 1371 |
const AffineConstraints<Number> &constraints, |
| 1372 |
const AdditionalDataType &matrix_free_additional_data); |
| 1373 |
|
| 1374 |
/** |
| 1375 |
* Compute the renumbering vector needed by the matrix_free_data_locality() |
| 1376 |
* function. |
| 1377 |
* Does not perform the renumbering on the @p DoFHandler dofs but returns the |
| 1378 |
* renumbering vector. |
| 1379 |
*/ |
| 1380 |
template <int dim, |
| 1381 |
int spacedim, |
| 1382 |
typename Number, |
| 1383 |
typename VectorizedArrayType> |
| 1384 |
std::vector<types::global_dof_index> |
| 1385 |
compute_matrix_free_data_locality( |
| 1386 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 1387 |
const MatrixFree<dim, Number, VectorizedArrayType> &matrix_free); |
| 1388 |
|
| 1389 |
/** |
| 1390 |
* Compute the renumbering vector needed by the matrix_free_data_locality() |
| 1391 |
* function. |
| 1392 |
* Does not perform the renumbering on the @p DoFHandler dofs but returns the |
| 1393 |
* renumbering vector. |
| 1394 |
*/ |
| 1395 |
template <int dim, int spacedim, typename Number, typename AdditionalDataType> |
| 1396 |
std::vector<types::global_dof_index> |
| 1397 |
compute_matrix_free_data_locality( |
| 1398 |
const DoFHandler<dim, spacedim> &dof_handler, |
| 1399 |
const AffineConstraints<Number> &constraints, |
| 1400 |
const AdditionalDataType &matrix_free_additional_data); |
| 1401 |
|
| 1402 |
/** |
| 1403 |
* @} |
| 1404 |
*/ |
| 1405 |
|
| 1406 |
|
| 1407 |
/** |
| 1408 |
* Exception |
| 1409 |
* |
| 1410 |
* @ingroup Exceptions |
| 1411 |
*/ |
| 1412 |
DeclExceptionMsg(ExcDoFHandlerNotInitialized, |
| 1413 |
"The DoFHandler on which this function should work has not " |
| 1414 |
"been initialized, i.e., it doesn't appear that DoF indices " |
| 1415 |
"have been distributed on it."); |
| 1416 |
|
| 1417 |
/** |
| 1418 |
* Exception |
| 1419 |
* |
| 1420 |
* @ingroup Exceptions |
| 1421 |
*/ |
| 1422 |
DeclException0(ExcInvalidComponentOrder); |
| 1423 |
|
| 1424 |
/** |
| 1425 |
* The function is only implemented for Discontinuous Galerkin Finite |
| 1426 |
* elements. |
| 1427 |
* |
| 1428 |
* @ingroup Exceptions |
| 1429 |
*/ |
| 1430 |
DeclException0(ExcNotDGFEM); |
| 1431 |
} // namespace DoFRenumbering |
| 1432 |
|
| 1433 |
|
| 1434 |
DEAL_II_NAMESPACE_CLOSE |
| 1435 |
|
| 1436 |
#endif |