// ------------------------------------------------------------------------ // // SPDX-License-Identifier: LGPL-2.1-or-later // Copyright (C) 2016 - 2024 by the deal.II authors // // This file is part of the deal.II library. // // Part of the source code is dual licensed under Apache-2.0 WITH // LLVM-exception OR LGPL-2.1-or-later. Detailed license information // governing the source code and code contributions can be found in // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. // // ------------------------------------------------------------------------ #ifndef dealii_mg_transfer_matrix_free_h #define dealii_mg_transfer_matrix_free_h #include #include #include #include #include #include #include #include #include #include DEAL_II_NAMESPACE_OPEN /** * @addtogroup mg * @{ */ /** * Implementation of the MGTransferBase interface for which the transfer * operations is implemented in a matrix-free way based on the interpolation * matrices of the underlying finite element. This requires considerably less * memory than MGTransferPrebuilt and can also be considerably faster than * that variant. * * This class currently only works for tensor-product finite elements based on * FE_Q and FE_DGQ elements, including systems involving multiple components * of one of these elements. Systems with different elements or other elements * are currently not implemented. */ template class MGTransferMatrixFree : public MGLevelGlobalTransfer> { public: /** * Constructor without constraint matrices. Use this constructor only with * discontinuous finite elements or with no local refinement. */ MGTransferMatrixFree(); /** * Constructor with constraints. Equivalent to the default constructor * followed by initialize_constraints(). */ MGTransferMatrixFree(const MGConstrainedDoFs &mg_constrained_dofs); /** * Destructor. */ virtual ~MGTransferMatrixFree() override = default; /** * Initialize the constraints to be used in build(). */ void initialize_constraints(const MGConstrainedDoFs &mg_constrained_dofs); /** * Reset the object to the state it had right after the default constructor. */ void clear(); /** * Actually build the information for the prolongation for each level. * * The optional second argument of external partitioners allows the user to * suggest vector partitioning on the levels. In case the partitioners * are found to contain all ghost unknowns that are visited through the * transfer, the given partitioners are chosen. This ensures compatibility * of vectors during prolongate and restrict with external partitioners as * given by the user, which in turn saves some copy operations. However, in * case there are unknowns missing -- and this is typically the case at some * point during h-coarsening since processors will need to drop out and * thus children's unknowns on some processor will be needed as ghosts to a * parent cell on another processor -- the provided external partitioners are * ignored and internal variants are used instead. */ void build(const DoFHandler &dof_handler, const std::vector> &external_partitioners = std::vector>()); /** * Same as above but taking a lambda for initializing vector instead of * partitioners. */ void build(const DoFHandler &dof_handler, const std::function &)> &initialize_dof_vector); /** * Prolongate a vector from level to_level-1 to level * to_level using the embedding matrices of the underlying finite * element. The previous content of dst is overwritten. * * @param to_level The index of the level to prolongate to, which is the * level of @p dst. * * @param src is a vector with as many elements as there are degrees of * freedom on the coarser level involved. * * @param dst has as many elements as there are degrees of freedom on the * finer level. */ virtual void prolongate( const unsigned int to_level, LinearAlgebra::distributed::Vector &dst, const LinearAlgebra::distributed::Vector &src) const override; virtual void prolongate_and_add( const unsigned int to_level, LinearAlgebra::distributed::Vector &dst, const LinearAlgebra::distributed::Vector &src) const override; /** * Restrict a vector from level from_level to level * from_level-1 using the transpose operation of the prolongate() * method. If the region covered by cells on level from_level is * smaller than that of level from_level-1 (local refinement), then * some degrees of freedom in dst are active and will not be * altered. For the other degrees of freedom, the result of the restriction * is added. * * @param from_level The index of the level to restrict from, which is the * level of @p src. * * @param src is a vector with as many elements as there are degrees of * freedom on the finer level involved. * * @param dst has as many elements as there are degrees of freedom on the * coarser level. */ virtual void restrict_and_add( const unsigned int from_level, LinearAlgebra::distributed::Vector &dst, const LinearAlgebra::distributed::Vector &src) const override; /** * Interpolate fine-mesh field @p src to each multigrid level in * @p dof_handler and store the result in @p dst. This function is different * from restriction, where a weighted residual is * transferred to a coarser level (transposition of prolongation matrix). * * The argument @p dst has to be initialized with the correct size according * to the number of levels of the triangulation. * * If an inner vector of @p dst is empty or has incorrect locally owned size, * it will be resized to locally relevant degrees of freedom on each level. * * The use of this function is demonstrated in step-66. */ template void interpolate_to_mg( const DoFHandler &dof_handler, MGLevelObject> &dst, const BlockVectorType2 &src) const; /** * Memory used by this object. */ std::size_t memory_consumption() const; private: /** * A variable storing the degree of the finite element contained in the * DoFHandler passed to build(). The selection of the computational kernel is * based on this number. */ unsigned int fe_degree; /** * A variable storing whether the element is continuous and there is a joint * degree of freedom in the center of the 1d line. */ bool element_is_continuous; /** * A variable storing the number of components in the finite element contained * in the DoFHandler passed to build(). */ unsigned int n_components; /** * A variable storing the number of degrees of freedom on all child cells. It * is 2dim*fe.n_dofs_per_cell() for DG elements and * somewhat less for continuous elements. */ unsigned int n_child_cell_dofs; /** * This variable holds the indices for cells on a given level, extracted from * DoFHandler for fast access. All DoF indices on a given level are stored as * a plain array (since this class assumes constant DoFs per cell). To index * into this array, use the cell number times dofs_per_cell. * * This array first is arranged such that all locally owned level cells come * first (found in the variable n_owned_level_cells) and then other cells * necessary for the transfer to the next level. */ std::vector> level_dof_indices; /** * A variable storing the connectivity from parent to child cell numbers for * each level. */ std::vector>> parent_child_connect; /** * A variable storing the number of cells owned on a given process (sets the * bounds for the worker loops) for each level. */ std::vector n_owned_level_cells; /** * This variable holds the one-dimensional embedding (prolongation) matrix * from parent element to all the children. */ AlignedVector> prolongation_matrix_1d; /** * This variable holds the temporary values for the tensor evaluation */ mutable AlignedVector> evaluation_data; /** * For continuous elements, restriction is not additive and we need to * weight the result at the end of prolongation (and at the start of * restriction) by the valence of the degrees of freedom, i.e., on how many * elements they appear. We store the data in vectorized form to allow for * cheap access. Moreover, we utilize the fact that we only need to store * 3dim indices. * * Data is organized in terms of each level (outer vector) and the cells on * each level (inner vector). */ std::vector>> weights_on_refined; /** * A variable storing the local indices of Dirichlet boundary conditions on * cells for all levels (outer index), the cells within the levels (second * index), and the indices on the cell (inner index). */ std::vector>> dirichlet_indices; /** * A vector that holds shared pointers to the partitioners of the * transfer. These partitioners might be shared with what was passed in from * the outside through build() or be shared with the level vectors inherited * from MGLevelGlobalTransfer. */ MGLevelObject> vector_partitioners; /** * Perform the prolongation operation. */ template void do_prolongate_add( const unsigned int to_level, LinearAlgebra::distributed::Vector &dst, const LinearAlgebra::distributed::Vector &src) const; /** * Performs the restriction operation. */ template void do_restrict_add(const unsigned int from_level, LinearAlgebra::distributed::Vector &dst, const LinearAlgebra::distributed::Vector &src) const; }; /** * Base class of MGTransferBlockMatrixFree. While MGTransferBlockMatrixFree * contains all the setup routines of the transfer operators for the blocks, * this class simply applies them, e.g., for restricting and prolongating. */ template class MGTransferBlockMatrixFreeBase : public MGTransferBase> { public: MGTransferBlockMatrixFreeBase(const bool same_for_all) : same_for_all(same_for_all) {} /** * Prolongate a vector from level to_level-1 to level * to_level using the embedding matrices of the underlying finite * element. The previous content of dst is overwritten. * * @param to_level The index of the level to prolongate to, which is the * level of @p dst. * * @param src is a vector with as many elements as there are degrees of * freedom on the coarser level involved. * * @param dst has as many elements as there are degrees of freedom on the * finer level. */ virtual void prolongate( const unsigned int to_level, LinearAlgebra::distributed::BlockVector &dst, const LinearAlgebra::distributed::BlockVector &src) const override; virtual void prolongate_and_add( const unsigned int to_level, LinearAlgebra::distributed::BlockVector &dst, const LinearAlgebra::distributed::BlockVector &src) const override; /** * Restrict a vector from level from_level to level * from_level-1 using the transpose operation of the prolongate() * method. If the region covered by cells on level from_level is * smaller than that of level from_level-1 (local refinement), then * some degrees of freedom in dst are active and will not be * altered. For the other degrees of freedom, the result of the restriction * is added. * * @param from_level The index of the level to restrict from, which is the * level of @p src. * * @param src is a vector with as many elements as there are degrees of * freedom on the finer level involved. * * @param dst has as many elements as there are degrees of freedom on the * coarser level. */ virtual void restrict_and_add( const unsigned int from_level, LinearAlgebra::distributed::BlockVector &dst, const LinearAlgebra::distributed::BlockVector &src) const override; /** * Transfer from a block-vector on the global grid to block-vectors defined * on each of the levels separately for active degrees of freedom. * In particular, for a globally refined mesh only the finest level in @p dst * is filled as a plain copy of @p src. All the other level objects are left * untouched. * * This function will initialize @p dst accordingly if needed as required by * the Multigrid class. */ template void copy_to_mg( const DoFHandler &dof_handler, MGLevelObject> &dst, const BlockVectorType2 &src) const; /** * Same as above for the case that each block has its own DoFHandler. */ template void copy_to_mg( const std::vector *> &dof_handler, MGLevelObject> &dst, const BlockVectorType2 &src) const; /** * Transfer from multi-level block-vector to normal vector. */ template void copy_from_mg( const DoFHandler &dof_handler, BlockVectorType2 &dst, const MGLevelObject> &src) const; /** * Same as above for the case that each block has its own DoFHandler. */ template void copy_from_mg( const std::vector *> &dof_handler, BlockVectorType2 &dst, const MGLevelObject> &src) const; /** * This class can both be used with a single DoFHandler * or a separate DoFHandler for each block. */ static const bool supports_dof_handler_vector = true; protected: /** * Return the right non-block transfer operator. Has to be implemented by * the derived class. */ virtual const TransferType & get_matrix_free_transfer(const unsigned int b) const = 0; /** * A flag to indicate whether the same DoFHandler is used for all * the components or if each block has its own DoFHandler. */ const bool same_for_all; }; /** * Implementation of the MGTransferBase interface for which the transfer * operations is implemented in a matrix-free way based on the interpolation * matrices of the underlying finite element. This requires considerably less * memory than MGTransferPrebuilt and can also be considerably faster than * that variant. * * This class works with LinearAlgebra::distributed::BlockVector and * performs exactly the same transfer operations for each block as * MGTransferMatrixFree. * Both the cases that the same DoFHandler is used for all the blocks * and that each block uses its own DoFHandler are supported. */ template class MGTransferBlockMatrixFree : public MGTransferBlockMatrixFreeBase> { public: /** * Constructor without constraint matrices. Use this constructor only with * discontinuous finite elements or with no local refinement. */ MGTransferBlockMatrixFree() = default; /** * Constructor with constraints. Equivalent to the default constructor * followed by initialize_constraints(). */ MGTransferBlockMatrixFree(const MGConstrainedDoFs &mg_constrained_dofs); /** * Same as above for the case that each block has its own DoFHandler. */ MGTransferBlockMatrixFree( const std::vector &mg_constrained_dofs); /** * Destructor. */ virtual ~MGTransferBlockMatrixFree() override = default; /** * Initialize the constraints to be used in build(). */ void initialize_constraints(const MGConstrainedDoFs &mg_constrained_dofs); /** * Same as above for the case that each block has its own DoFHandler. */ void initialize_constraints( const std::vector &mg_constrained_dofs); /** * Reset the object to the state it had right after the default constructor. */ void clear(); /** * Actually build the information for the prolongation for each level. */ void build(const DoFHandler &dof_handler); /** * Same as above for the case that each block has its own DoFHandler. */ void build(const std::vector *> &dof_handler); /** * Memory used by this object. */ std::size_t memory_consumption() const; protected: const MGTransferMatrixFree & get_matrix_free_transfer(const unsigned int b) const override; private: /** * Non-block matrix-free versions of transfer operation. */ std::vector> matrix_free_transfer_vector; }; /** @} */ //------------------------ templated functions ------------------------- #ifndef DOXYGEN template template void MGTransferMatrixFree::interpolate_to_mg( const DoFHandler &dof_handler, MGLevelObject> &dst, const BlockVectorType2 &src) const { const unsigned int min_level = dst.min_level(); const unsigned int max_level = dst.max_level(); Assert(max_level == dof_handler.get_triangulation().n_global_levels() - 1, ExcDimensionMismatch( max_level, dof_handler.get_triangulation().n_global_levels() - 1)); const auto &fe = dof_handler.get_fe(); for (unsigned int level = min_level; level <= max_level; ++level) if (dst[level].size() != dof_handler.n_dofs(level) || dst[level].locally_owned_size() != dof_handler.locally_owned_mg_dofs(level).n_elements()) dst[level].reinit(this->vector_partitioners[level]); // copy fine level vector to active cells in MG hierarchy this->copy_to_mg(dof_handler, dst, src, true); // FIXME: maybe need to store hanging nodes constraints per level? // MGConstrainedDoFs does NOT keep this info right now, only periodicity // constraints... // do the transfer from level to level-1: dst[max_level].update_ghost_values(); for (unsigned int level = max_level; level > min_level; --level) { // auxiliary vector which always has ghost elements const LinearAlgebra::distributed::Vector *input = nullptr; LinearAlgebra::distributed::Vector ghosted_fine; if (dst[level].get_partitioner().get() == this->vector_partitioners[level].get()) input = &dst[level]; else { ghosted_fine.reinit(this->vector_partitioners[level]); ghosted_fine.copy_locally_owned_data_from(dst[level]); ghosted_fine.update_ghost_values(); input = &ghosted_fine; } std::vector dof_values_coarse(fe.n_dofs_per_cell()); Vector dof_values_fine(fe.n_dofs_per_cell()); Vector tmp(fe.n_dofs_per_cell()); std::vector dof_indices(fe.n_dofs_per_cell()); for (const auto &cell : dof_handler.cell_iterators_on_level(level - 1)) if (cell->is_locally_owned_on_level()) { // if we get to a cell without children (== active), we can // skip it as there values should be already set by the // equivalent of copy_to_mg() if (cell->is_active()) continue; std::fill(dof_values_coarse.begin(), dof_values_coarse.end(), 0.); for (unsigned int child = 0; child < cell->n_children(); ++child) { cell->child(child)->get_mg_dof_indices(dof_indices); internal::MGTransfer::resolve_identity_constraints( this->mg_constrained_dofs, level, dof_indices); for (unsigned int i = 0; i < fe.n_dofs_per_cell(); ++i) dof_values_fine(i) = (*input)(dof_indices[i]); fe.get_restriction_matrix(child, cell->refinement_case()) .vmult(tmp, dof_values_fine); for (unsigned int i = 0; i < fe.n_dofs_per_cell(); ++i) if (fe.restriction_is_additive(i)) dof_values_coarse[i] += tmp[i]; else if (tmp(i) != 0.) dof_values_coarse[i] = tmp[i]; } cell->get_mg_dof_indices(dof_indices); for (unsigned int i = 0; i < fe.n_dofs_per_cell(); ++i) if (dof_handler.locally_owned_mg_dofs(level - 1).is_element( dof_indices[i])) dst[level - 1](dof_indices[i]) = dof_values_coarse[i]; } dst[level - 1].update_ghost_values(); } for (unsigned int level = min_level; level <= max_level; ++level) dst[level].zero_out_ghost_values(); } template template void MGTransferBlockMatrixFreeBase::copy_to_mg( const DoFHandler &dof_handler, MGLevelObject> &dst, const BlockVectorType2 &src) const { Assert(same_for_all, ExcMessage( "This object was initialized with support for usage with one " "DoFHandler for each block, but this method assumes that " "the same DoFHandler is used for all the blocks!")); const std::vector *> mg_dofs(src.n_blocks(), &dof_handler); copy_to_mg(mg_dofs, dst, src); } template template void MGTransferBlockMatrixFreeBase::copy_to_mg( const std::vector *> &dof_handler, MGLevelObject> &dst, const BlockVectorType2 &src) const { const unsigned int n_blocks = src.n_blocks(); AssertDimension(dof_handler.size(), n_blocks); if (n_blocks == 0) return; const unsigned int min_level = dst.min_level(); const unsigned int max_level = dst.max_level(); for (unsigned int level = min_level; level <= max_level; ++level) if (dst[level].n_blocks() != n_blocks) dst[level].reinit(n_blocks); // FIXME: this a quite ugly as we need a temporary object: MGLevelObject> dst_non_block( min_level, max_level); for (unsigned int b = 0; b < n_blocks; ++b) { const unsigned int data_block = same_for_all ? 0 : b; get_matrix_free_transfer(data_block) .copy_to_mg(*dof_handler[b], dst_non_block, src.block(b)); for (unsigned int l = min_level; l <= max_level; ++l) dst[l].block(b) = dst_non_block[l]; } for (unsigned int level = min_level; level <= max_level; ++level) dst[level].collect_sizes(); } template template void MGTransferBlockMatrixFreeBase::copy_from_mg( const DoFHandler &dof_handler, BlockVectorType2 &dst, const MGLevelObject> &src) const { Assert(same_for_all, ExcMessage( "This object was initialized with support for usage with one " "DoFHandler for each block, but this method assumes that " "the same DoFHandler is used for all the blocks!")); const std::vector *> mg_dofs(dst.n_blocks(), &dof_handler); copy_from_mg(mg_dofs, dst, src); } template template void MGTransferBlockMatrixFreeBase::copy_from_mg( const std::vector *> &dof_handler, BlockVectorType2 &dst, const MGLevelObject> &src) const { const unsigned int n_blocks = dst.n_blocks(); AssertDimension(dof_handler.size(), n_blocks); if (n_blocks == 0) return; const unsigned int min_level = src.min_level(); const unsigned int max_level = src.max_level(); for (unsigned int l = min_level; l <= max_level; ++l) AssertDimension(src[l].n_blocks(), dst.n_blocks()); // FIXME: this a quite ugly as we need a temporary object: MGLevelObject> src_non_block( min_level, max_level); for (unsigned int b = 0; b < n_blocks; ++b) { for (unsigned int l = min_level; l <= max_level; ++l) { src_non_block[l].reinit(src[l].block(b)); src_non_block[l] = src[l].block(b); } const unsigned int data_block = same_for_all ? 0 : b; get_matrix_free_transfer(data_block) .copy_from_mg(*dof_handler[b], dst.block(b), src_non_block); } } #endif // DOXYGEN DEAL_II_NAMESPACE_CLOSE #endif