Debian Codegraph @

include/deal.II/dofs/dof_renumbering.h

raw
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> &center,
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> &center,
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> &center,
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