<commit_before>//---------------------------------------------------------------------------
//    $Id$
//    Version: $Name$
//
//    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 by the deal.II authors
//
//    This file is subject to QPL and may not be  distributed
//    without copyright and license information. Please refer
//    to the file deal.II/doc/license.html for the  text  and
//    further information on this license.
//
//---------------------------------------------------------------------------
#ifndef __deal2__dof_renumbering_h
#define __deal2__dof_renumbering_h


#include <base/config.h>
#include <base/exceptions.h>
#include <base/point.h>
#include <dofs/dof_handler.h>
#include <multigrid/mg_dof_handler.h>

#include <vector>

DEAL_II_NAMESPACE_OPEN

/**
 * Implementation of a number of renumbering algorithms for the degrees of
 * freedom on a triangulation.
 *
 * <h3>Cuthill-McKee like algorithms</h3>
 *
 * Within this class, the Cuthill-McKee algorithm is implemented. It
 * starts at a degree of freedom, searches the other DoFs for those
 * which are couple with the one we started with and numbers these in
 * a certain way. It then finds the second level of DoFs, namely those
 * that couple with those of the previous level (which were those that
 * coupled with the initial DoF) and numbers these. And so on. For the
 * details of the algorithm, especially the numbering within each
 * level, we refer the reader to the book of Schwarz (H.R.Schwarz:
 * Methode der finiten Elemente). The reverse Cuthill-McKee algorithm
 * does the same job, but numbers all elements in the reverse order.
 *
 * These algorithms have one major drawback: they require a good
 * starting point, i.e. the degree of freedom index afterwards to be
 * numbered zero. This can thus be given by the user, e.g. by
 * exploiting knowledge of the actual topology of the domain. It is
 * also possible to give several starting indices, which may be used
 * to simulate a simple upstream numbering (by giving the inflow dofs
 * as starting values) or to make preconditioning faster (by letting
 * the dirichlet boundary indices be starting points).
 *
 * If no starting index is given, one is chosen by the program, namely
 * one with the smallest coordination number (the coordination number
 * is the number of other dofs this dof couples with). This dof is
 * usually located on the boundary of the domain. There is, however,
 * large ambiguity in this when using the hierarchical meshes used in
 * this library, since in most cases the computational domain is not
 * approximated by tilting and deforming elements and by plugging
 * together variable numbers of elements at vertices, but rather by
 * hierarchical refinement. There is therefore a large number of dofs
 * with equal coordination numbers. The renumbering algorithms will
 * therefore not give optimal results.
 *
 * In the book of Schwarz (H.R.Schwarz: Methode der finiten Elemente),
 * it is advised to test many starting points, if possible all with
 * the smallest coordination number and also those with slightly
 * higher numbers. However, this seems only possible for meshes with
 * at most several dozen or a few hundred elements found in small
 * engineering problems of the early 1980s (the second edition was
 * published in 1984), but certainly not with those used in this
 * library, featuring several 10,000 to a few 100,000 elements.
 *
 * On the other hand, the need to reduce the bandwidth has decreased
 * since with the mentioned number of cells, only iterative solution
 * methods are able to solve the resulting matrix systems. These,
 * however, are not so demanding with respect to the bandwidth as
 * direct solvers used for smaller problems. Things like upstream
 * numbering become much more important in recent times, so the
 * suboptimality of the renumbering algorithms is not that important
 * any more.
 *
 * 
 * <h4>Implementation of renumbering schemes</h4>
 *
 * The renumbering algorithms need quite a lot of memory, since they
 * have to store for each dof with which other dofs it couples. This
 * is done using a SparsityPattern object used to store the sparsity
 * pattern of matrices. It is not useful for the user to do anything
 * between distributing the dofs and renumbering, i.e. the calls to
 * DoFHandler::distribute_dofs and DoFHandler::renumber_dofs should
 * follow each other immediately. If you try to create a sparsity
 * pattern or anything else in between, these will be invalid
 * afterwards.
 *
 * The renumbering may take care of dof-to-dof couplings only induced
 * by eliminating constraints. In addition to the memory consumption
 * mentioned above, this also takes quite some computational time, but
 * it may be switched off upon calling the @p renumber_dofs
 * function. This will then give inferior results, since knots in the
 * graph (representing dofs) are not found to be neighbors even if
 * they would be after condensation.
 * 
 * The renumbering algorithms work on a purely algebraic basis, due to
 * the isomorphism between the graph theoretical groundwork underlying
 * the algorithms and binary matrices (matrices of which the entries
 * are binary values) represented by the sparsity patterns. In
 * special, the algorithms do not try to exploit topological knowledge
 * (e.g. corner detection) to find appropriate starting points. This
 * way, however, they work in arbitrary space dimension.
 *
 * If you want to give starting points, you may give a list of dof
 * indices which will form the first step of the renumbering. The dofs
 * of the list will be consecutively numbered starting with zero,
 * i.e. this list is not renumbered according to the coordination
 * number of the nodes. Indices not in the allowed range are
 * deleted. If no index is allowed, the algorithm will search for its
 * own starting point.
 *
 * 
 * <h4>Results of renumbering</h4>
 *
 * The renumbering schemes mentioned above do not lead to optimal
 * results.  However, after all there is no algorithm that
 * accomplishes this within reasonable time. There are situations
 * where the lack of optimality even leads to worse results than with
 * the original, crude, levelwise numering scheme; one of these
 * examples is a mesh of four cells of which always those cells are
 * refined which are neighbors to the center (you may call this mesh a
 * `zoom in' mesh). In one such example the bandwidth was increased by
 * about 50 per cent.
 *
 * In most other cases, the bandwith is reduced significantly. The reduction
 * is the better the less structured the grid is. With one grid where the
 * cells were refined according to a random driven algorithm, the bandwidth
 * was reduced by a factor of six.
 *
 * Using the constraint information usually leads to reductions in bandwidth
 * of 10 or 20 per cent, but may for some very unstructured grids also lead
 * to an increase. You have to weigh the decrease in your case with the time
 * spent to use the constraint information, which usually is several times
 * longer than the `pure' renumbering algorithm.
 *
 * In almost all cases, the renumbering scheme finds a corner to start with.
 * Since there is more than one corner in most grids and since even an
 * interior degree of freedom may be a better starting point, giving the
 * starting point by the user may be a viable way if you have a simple
 * scheme to derive a suitable point (e.g. by successively taking the
 * third child of the cell top left of the coarsest level, taking its
 * third vertex and the dof index thereof, if you want the top left corner
 * vertex). If you do not know beforehand what your grid will look like
 * (e.g. when using adaptive algorithms), searching a best starting point
 * may be difficult, however, and in many cases will not justify the effort.
 *
 *
 * <h3>Component-wise numbering</h3>
 *
 * For finite elements composed of several base elements using the FESystem
 * class, or for elements which provide several components themselves, it
 * may be of interest to sort the DoF indices by component. This will then
 * bring out the block matrix structure, since otherwise the degrees of freedom
 * are numbered cell-wise without taking into account that they may belong to
 * different components.
 *
 * This kind of numbering may be obtained by calling the
 * component_wise() function of this class. Since it does not touch
 * the order of indices within each, it may be worthwhile to first
 * renumber using the Cuthill-McKee or a similar algorithm and
 * afterwards renumbering component-wise. This will bring out the
 * matrix structure and additionally have a good numbering within each
 * block.
 *
 *
 * <h3>Cell-wise numbering</h3>
 *<commit_msg>Augment documentation<commit_after>//---------------------------------------------------------------------------
//    $Id$
//    Version: $Name$
//
//    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 by the deal.II authors
//
//    This file is subject to QPL and may not be  distributed
//    without copyright and license information. Please refer
//    to the file deal.II/doc/license.html for the  text  and
//    further information on this license.
//
//---------------------------------------------------------------------------
#ifndef __deal2__dof_renumbering_h
#define __deal2__dof_renumbering_h


#include <base/config.h>
#include <base/exceptions.h>
#include <base/point.h>
#include <dofs/dof_handler.h>
#include <multigrid/mg_dof_handler.h>

#include <vector>

DEAL_II_NAMESPACE_OPEN

/**
 * Implementation of a number of renumbering algorithms for the degrees of
 * freedom on a triangulation.
 *
 * <h3>Cuthill-McKee like algorithms</h3>
 *
 * Within this class, the Cuthill-McKee algorithm is implemented. It
 * starts at a degree of freedom, searches the other DoFs for those
 * which are couple with the one we started with and numbers these in
 * a certain way. It then finds the second level of DoFs, namely those
 * that couple with those of the previous level (which were those that
 * coupled with the initial DoF) and numbers these. And so on. For the
 * details of the algorithm, especially the numbering within each
 * level, we refer the reader to the book of Schwarz (H.R.Schwarz:
 * Methode der finiten Elemente). The reverse Cuthill-McKee algorithm
 * does the same job, but numbers all elements in the reverse order.
 *
 * These algorithms have one major drawback: they require a good
 * starting point, i.e. the degree of freedom index afterwards to be
 * numbered zero. This can thus be given by the user, e.g. by
 * exploiting knowledge of the actual topology of the domain. It is
 * also possible to give several starting indices, which may be used
 * to simulate a simple upstream numbering (by giving the inflow dofs
 * as starting values) or to make preconditioning faster (by letting
 * the dirichlet boundary indices be starting points).
 *
 * If no starting index is given, one is chosen by the program, namely
 * one with the smallest coordination number (the coordination number
 * is the number of other dofs this dof couples with). This dof is
 * usually located on the boundary of the domain. There is, however,
 * large ambiguity in this when using the hierarchical meshes used in
 * this library, since in most cases the computational domain is not
 * approximated by tilting and deforming elements and by plugging
 * together variable numbers of elements at vertices, but rather by
 * hierarchical refinement. There is therefore a large number of dofs
 * with equal coordination numbers. The renumbering algorithms will
 * therefore not give optimal results.
 *
 * In the book of Schwarz (H.R.Schwarz: Methode der finiten Elemente),
 * it is advised to test many starting points, if possible all with
 * the smallest coordination number and also those with slightly
 * higher numbers. However, this seems only possible for meshes with
 * at most several dozen or a few hundred elements found in small
 * engineering problems of the early 1980s (the second edition was
 * published in 1984), but certainly not with those used in this
 * library, featuring several 10,000 to a few 100,000 elements.
 *
 * On the other hand, the need to reduce the bandwidth has decreased
 * since with the mentioned number of cells, only iterative solution
 * methods are able to solve the resulting matrix systems. These,
 * however, are not so demanding with respect to the bandwidth as
 * direct solvers used for smaller problems. Things like upstream
 * numbering become much more important in recent times, so the
 * suboptimality of the renumbering algorithms is not that important
 * any more.
 *
 * 
 * <h4>Implementation of renumbering schemes</h4>
 *
 * The renumbering algorithms need quite a lot of memory, since they
 * have to store for each dof with which other dofs it couples. This
 * is done using a SparsityPattern object used to store the sparsity
 * pattern of matrices. It is not useful for the user to do anything
 * between distributing the dofs and renumbering, i.e. the calls to
 * DoFHandler::distribute_dofs and DoFHandler::renumber_dofs should
 * follow each other immediately. If you try to create a sparsity
 * pattern or anything else in between, these will be invalid
 * afterwards.
 *
 * The renumbering may take care of dof-to-dof couplings only induced
 * by eliminating constraints. In addition to the memory consumption
 * mentioned above, this also takes quite some computational time, but
 * it may be switched off upon calling the @p renumber_dofs
 * function. This will then give inferior results, since knots in the
 * graph (representing dofs) are not found to be neighbors even if
 * they would be after condensation.
 * 
 * The renumbering algorithms work on a purely algebraic basis, due to
 * the isomorphism between the graph theoretical groundwork underlying
 * the algorithms and binary matrices (matrices of which the entries
 * are binary values) represented by the sparsity patterns. In
 * special, the algorithms do not try to exploit topological knowledge
 * (e.g. corner detection) to find appropriate starting points. This
 * way, however, they work in arbitrary space dimension.
 *
 * If you want to give starting points, you may give a list of dof
 * indices which will form the first step of the renumbering. The dofs
 * of the list will be consecutively numbered starting with zero,
 * i.e. this list is not renumbered according to the coordination
 * number of the nodes. Indices not in the allowed range are
 * deleted. If no index is allowed, the algorithm will search for its
 * own starting point.
 *
 * 
 * <h4>Results of renumbering</h4>
 *
 * The renumbering schemes mentioned above do not lead to optimal
 * results.  However, after all there is no algorithm that
 * accomplishes this within reasonable time. There are situations
 * where the lack of optimality even leads to worse results than with
 * the original, crude, levelwise numering scheme; one of these
 * examples is a mesh of four cells of which always those cells are
 * refined which are neighbors to the center (you may call this mesh a
 * `zoom in' mesh). In one such example the bandwidth was increased by
 * about 50 per cent.
 *
 * In most other cases, the bandwith is reduced significantly. The reduction
 * is the better the less structured the grid is. With one grid where the
 * cells were refined according to a random driven algorithm, the bandwidth
 * was reduced by a factor of six.
 *
 * Using the constraint information usually leads to reductions in bandwidth
 * of 10 or 20 per cent, but may for some very unstructured grids also lead
 * to an increase. You have to weigh the decrease in your case with the time
 * spent to use the constraint information, which usually is several times
 * longer than the `pure' renumbering algorithm.
 *
 * In almost all cases, the renumbering scheme finds a corner to start with.
 * Since there is more than one corner in most grids and since even an
 * interior degree of freedom may be a better starting point, giving the
 * starting point by the user may be a viable way if you have a simple
 * scheme to derive a suitable point (e.g. by successively taking the
 * third child of the cell top left of the coarsest level, taking its
 * third vertex and the dof index thereof, if you want the top left corner
 * vertex). If you do not know beforehand what your grid will look like
 * (e.g. when using adaptive algorithms), searching a best starting point
 * may be difficult, however, and in many cases will not justify the effort.
 *
 *
 * <h3>Component-wise numbering</h3>
 *
 * For finite elements composed of several base elements using the FESystem
 * class, or for elements which provide several components themselves, it
 * may be of interest to sort the DoF indices by component. This will then
 * bring out the block matrix structure, since otherwise the degrees of freedom
 * are numbered cell-wise without taking into account that they may belong to
 * different components.
 *
 * This kind of numbering may be obtained by calling the
 * component_wise() function of this class. Since it does not touch
 * the order of indices within each, it may be worthwhile to first
 * renumber using the Cuthill-McKee or a similar algorithm and
 * afterwards renumbering component-wise. This will bring out the
 * matrix structure and additionally have a good numbering within each
 * block.
 *
 * The component_wise() function allows not only to honor enumeration based on
 * vector components, but also allows to group together vector components into
 * "blocks". See @ref GlossComponent vs @ref GlossBlock for a description of
 * the difference.
 *
 *
 * <h3>Cell-wise numbering</h3>
 *
{'fraction_non_alphanumeric': 0.06610732586294274, 'fraction_numerical': 0.006869756179965088, 'mean_word_length': 3.6237958864878936, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '405755', 'n_tokens_mistral': 4518, 'n_tokens_neox': 4270, 'n_words': 2596}