dof_renumbering.h

Go to the documentation of this file.

// -----------------------------------------------------------------------------
//
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception OR LGPL-2.1-or-later
// Copyright (C) 2003 - 2025 by the deal.II authors
//
// This file is part of the deal.II library.
//
// Detailed license information governing the source code and contributions
// can be found in LICENSE.md and CONTRIBUTING.md at the top level directory.
//
// -----------------------------------------------------------------------------
 
#ifndef dealii_dof_renumbering_h
#define dealii_dof_renumbering_h
 
 
#include <deal.II/base/config.h>
 
#include <deal.II/base/exceptions.h>
#include <deal.II/base/point.h>
 
#include <deal.II/dofs/dof_handler.h>
 
#include <vector>
 
DEAL_II_NAMESPACE_OPEN
 
#ifndef DOXYGEN
// forward declaration
template <int, typename, typename>
class MatrixFree;
#endif
 
namespace DoFRenumbering
{
  template <class Iterator, int dim>
  struct CompareDownstream
  {
    CompareDownstream(const Tensor<1, dim> &dir)
      : dir(dir)
    {}
    bool
    operator()(const Iterator &c1, const Iterator &c2) const
    {
      const Tensor<1, dim> diff = c2->center() - c1->center();
      return (diff * dir > 0);
    }
 
  private:
    const Tensor<1, dim> dir;
  };
 
 
  template <int dim>
  struct ComparePointwiseDownstream
  {
    ComparePointwiseDownstream(const Tensor<1, dim> &dir)
      : dir(dir)
    {}
    bool
    operator()(const std::pair<Point<dim>, types::global_dof_index> &c1,
               const std::pair<Point<dim>, types::global_dof_index> &c2) const
    {
      const Tensor<1, dim> diff = c2.first - c1.first;
      return (diff * dir > 0 || (diff * dir == 0 && c1.second < c2.second));
    }
 
  private:
    const Tensor<1, dim> dir;
  };
 
 
 
  namespace boost
  {
    template <int dim, int spacedim>
    void
    Cuthill_McKee(DoFHandler<dim, spacedim> &dof_handler,
                  const bool                 reversed_numbering = false,
                  const bool                 use_constraints    = false);
 
    template <int dim, int spacedim>
    void
    compute_Cuthill_McKee(std::vector<types::global_dof_index> &new_dof_indices,
                          const DoFHandler<dim, spacedim> &,
                          const bool reversed_numbering = false,
                          const bool use_constraints    = false);
 
    template <int dim, int spacedim>
    void
    king_ordering(DoFHandler<dim, spacedim> &dof_handler,
                  const bool                 reversed_numbering = false,
                  const bool                 use_constraints    = false);
 
    template <int dim, int spacedim>
    void
    compute_king_ordering(std::vector<types::global_dof_index> &new_dof_indices,
                          const DoFHandler<dim, spacedim> &,
                          const bool reversed_numbering = false,
                          const bool use_constraints    = false);
 
    template <int dim, int spacedim>
    void
    minimum_degree(DoFHandler<dim, spacedim> &dof_handler,
                   const bool                 reversed_numbering = false,
                   const bool                 use_constraints    = false);
 
    template <int dim, int spacedim>
    void
    compute_minimum_degree(
      std::vector<types::global_dof_index> &new_dof_indices,
      const DoFHandler<dim, spacedim> &,
      const bool reversed_numbering = false,
      const bool use_constraints    = false);
  } // namespace boost
 
  template <int dim, int spacedim>
  void
  Cuthill_McKee(DoFHandler<dim, spacedim> &dof_handler,
                const bool                 reversed_numbering = false,
                const bool                 use_constraints    = false,
                const std::vector<types::global_dof_index> &starting_indices =
                  std::vector<types::global_dof_index>());
 
  template <int dim, int spacedim>
  void
  compute_Cuthill_McKee(
    std::vector<types::global_dof_index> &new_dof_indices,
    const DoFHandler<dim, spacedim> &,
    const bool                                  reversed_numbering = false,
    const bool                                  use_constraints    = false,
    const std::vector<types::global_dof_index> &starting_indices =
      std::vector<types::global_dof_index>(),
    const unsigned int level = numbers::invalid_unsigned_int);
 
  template <int dim, int spacedim>
  void
  Cuthill_McKee(DoFHandler<dim, spacedim> &dof_handler,
                const unsigned int         level,
                const bool                 reversed_numbering = false,
                const std::vector<types::global_dof_index> &starting_indices =
                  std::vector<types::global_dof_index>());
 
  template <int dim, int spacedim>
  void
  component_wise(DoFHandler<dim, spacedim>       &dof_handler,
                 const std::vector<unsigned int> &target_component =
                   std::vector<unsigned int>());
 
 
  template <int dim, int spacedim>
  void
  component_wise(DoFHandler<dim, spacedim>       &dof_handler,
                 const unsigned int               level,
                 const std::vector<unsigned int> &target_component =
                   std::vector<unsigned int>());
 
 
 
  template <int dim, int spacedim>
  void
  component_wise(DoFHandler<dim, spacedim> &dof_handler,
                 const std::vector<FEValuesExtractors::AnyExtractor> &order);
 
  template <int dim, int spacedim>
  void
  component_wise(DoFHandler<dim, spacedim> &dof_handler,
                 const unsigned int         level,
                 const std::vector<FEValuesExtractors::AnyExtractor> &order);
 
 
  template <int dim, int spacedim, typename CellIterator>
  types::global_dof_index
  compute_component_wise(std::vector<types::global_dof_index> &new_dof_indices,
                         const CellIterator                   &start,
                         const std_cxx20::type_identity_t<CellIterator> &end,
                         const std::vector<unsigned int> &target_component,
                         const bool                       is_level_operation);
 
  template <int dim, int spacedim>
  void
  block_wise(DoFHandler<dim, spacedim> &dof_handler);
 
  template <int dim, int spacedim>
  void
  block_wise(DoFHandler<dim, spacedim> &dof_handler, const unsigned int level);
 
  template <int dim, int spacedim, class IteratorType, class EndIteratorType>
  types::global_dof_index
  compute_block_wise(std::vector<types::global_dof_index> &new_dof_indices,
                     const IteratorType                   &start,
                     const EndIteratorType                &end,
                     const bool                            is_level_operation);
 
  template <int dim, int spacedim>
  void
  hierarchical(DoFHandler<dim, spacedim> &dof_handler);
 
  template <int dim, int spacedim>
  void
  cell_wise(
    DoFHandler<dim, spacedim> &dof_handler,
    const std::vector<typename DoFHandler<dim, spacedim>::active_cell_iterator>
      &cell_order);
 
  template <int dim, int spacedim>
  void
  compute_cell_wise(
    std::vector<types::global_dof_index> &renumbering,
    std::vector<types::global_dof_index> &inverse_renumbering,
    const DoFHandler<dim, spacedim>      &dof_handler,
    const std::vector<typename DoFHandler<dim, spacedim>::active_cell_iterator>
      &cell_order);
 
  template <int dim, int spacedim>
  void
  cell_wise(
    DoFHandler<dim, spacedim> &dof_handler,
    const unsigned int         level,
    const std::vector<typename DoFHandler<dim, spacedim>::level_cell_iterator>
      &cell_order);
 
  template <int dim, int spacedim>
  void
  compute_cell_wise(
    std::vector<types::global_dof_index> &renumbering,
    std::vector<types::global_dof_index> &inverse_renumbering,
    const DoFHandler<dim, spacedim>      &dof_handler,
    const unsigned int                    level,
    const std::vector<typename DoFHandler<dim, spacedim>::level_cell_iterator>
      &cell_order);
 
  template <int dim, int spacedim>
  void
  downstream(DoFHandler<dim, spacedim> &dof_handler,
             const Tensor<1, spacedim> &direction,
             const bool                 dof_wise_renumbering = false);
 
 
  template <int dim, int spacedim>
  void
  downstream(DoFHandler<dim, spacedim> &dof_handler,
             const unsigned int         level,
             const Tensor<1, spacedim> &direction,
             const bool                 dof_wise_renumbering = false);
 
  template <int dim, int spacedim>
  void
  compute_downstream(std::vector<types::global_dof_index> &new_dof_indices,
                     std::vector<types::global_dof_index> &reverse,
                     const DoFHandler<dim, spacedim>      &dof_handler,
                     const Tensor<1, spacedim>            &direction,
                     const bool dof_wise_renumbering);
 
  template <int dim, int spacedim>
  void
  compute_downstream(std::vector<types::global_dof_index> &new_dof_indices,
                     std::vector<types::global_dof_index> &reverse,
                     const DoFHandler<dim, spacedim>      &dof_handler,
                     const unsigned int                    level,
                     const Tensor<1, spacedim>            &direction,
                     const bool dof_wise_renumbering);
 
  template <int dim, int spacedim>
  void
  clockwise_dg(DoFHandler<dim, spacedim> &dof_handler,
               const Point<spacedim>     &center,
               const bool                 counter = false);
 
  template <int dim, int spacedim>
  void
  clockwise_dg(DoFHandler<dim, spacedim> &dof_handler,
               const unsigned int         level,
               const Point<spacedim>     &center,
               const bool                 counter = false);
 
  template <int dim, int spacedim>
  void
  compute_clockwise_dg(std::vector<types::global_dof_index> &new_dof_indices,
                       const DoFHandler<dim, spacedim>      &dof_handler,
                       const Point<spacedim>                &center,
                       const bool                            counter);
 
  template <int dim, int spacedim>
  void
  sort_selected_dofs_back(DoFHandler<dim, spacedim> &dof_handler,
                          const std::vector<bool>   &selected_dofs);
 
  template <int dim, int spacedim>
  void
  sort_selected_dofs_back(DoFHandler<dim, spacedim> &dof_handler,
                          const std::vector<bool>   &selected_dofs,
                          const unsigned int         level);
 
  template <int dim, int spacedim>
  void
  compute_sort_selected_dofs_back(
    std::vector<types::global_dof_index> &new_dof_indices,
    const DoFHandler<dim, spacedim>      &dof_handler,
    const std::vector<bool>              &selected_dofs);
 
  template <int dim, int spacedim>
  void
  compute_sort_selected_dofs_back(
    std::vector<types::global_dof_index> &new_dof_indices,
    const DoFHandler<dim, spacedim>      &dof_handler,
    const std::vector<bool>              &selected_dofs,
    const unsigned int                    level);
 
  template <int dim, int spacedim>
  void
  random(DoFHandler<dim, spacedim> &dof_handler);
 
  template <int dim, int spacedim>
  void
  random(DoFHandler<dim, spacedim> &dof_handler, const unsigned int level);
 
  template <int dim, int spacedim>
  void
  compute_random(std::vector<types::global_dof_index> &new_dof_indices,
                 const DoFHandler<dim, spacedim>      &dof_handler);
 
  template <int dim, int spacedim>
  void
  compute_random(std::vector<types::global_dof_index> &new_dof_indices,
                 const DoFHandler<dim, spacedim>      &dof_handler,
                 const unsigned int                    level);
 
  template <int dim, int spacedim>
  void
  subdomain_wise(DoFHandler<dim, spacedim> &dof_handler);
 
  template <int dim, int spacedim>
  void
  compute_subdomain_wise(std::vector<types::global_dof_index> &new_dof_indices,
                         const DoFHandler<dim, spacedim>      &dof_handler);
 
  template <int dim, int spacedim>
  void
  support_point_wise(DoFHandler<dim, spacedim> &dof_handler);
 
  template <int dim, int spacedim>
  void
  compute_support_point_wise(
    std::vector<types::global_dof_index> &new_dof_indices,
    const DoFHandler<dim, spacedim>      &dof_handler);
 
  template <int dim>
  void
  lexicographic(DoFHandler<dim> &dof_handler, const double tolerance = 1e-12);
 
  template <int dim>
  void
  compute_lexicographic(std::vector<types::global_dof_index> &new_dof_indices,
                        const DoFHandler<dim>                &handler,
                        const double tolerance = 1e-12);
 
  template <int dim,
            int spacedim,
            typename Number,
            typename VectorizedArrayType>
  void
  matrix_free_data_locality(
    DoFHandler<dim, spacedim>                          &dof_handler,
    const MatrixFree<dim, Number, VectorizedArrayType> &matrix_free);
 
  template <int dim, int spacedim, typename Number, typename AdditionalDataType>
  void
  matrix_free_data_locality(
    DoFHandler<dim, spacedim>       &dof_handler,
    const AffineConstraints<Number> &constraints,
    const AdditionalDataType        &matrix_free_additional_data);
 
  template <int dim,
            int spacedim,
            typename Number,
            typename VectorizedArrayType>
  std::vector<types::global_dof_index>
  compute_matrix_free_data_locality(
    const DoFHandler<dim, spacedim>                    &dof_handler,
    const MatrixFree<dim, Number, VectorizedArrayType> &matrix_free);
 
  template <int dim, int spacedim, typename Number, typename AdditionalDataType>
  std::vector<types::global_dof_index>
  compute_matrix_free_data_locality(
    const DoFHandler<dim, spacedim> &dof_handler,
    const AffineConstraints<Number> &constraints,
    const AdditionalDataType        &matrix_free_additional_data);
 
  DeclExceptionMsg(ExcDoFHandlerNotInitialized,
                   "The DoFHandler on which this function should work has not "
                   "been initialized, i.e., it doesn't appear that DoF indices "
                   "have been distributed on it.");
 
  DeclException0(ExcInvalidComponentOrder);
 
  DeclException0(ExcNotDGFEM);
} // namespace DoFRenumbering
 
 
DEAL_II_NAMESPACE_CLOSE
 
#endif