// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- // vi: set et ts=4 sw=2 sts=2: #ifndef DUNE_GALERKIN_HH #define DUNE_GALERKIN_HH #include "aggregates.hh" #include "pinfo.hh" #include #include #include #include #include namespace Dune { namespace Amg { /** * @addtogroup ISTL_PAAMG * * @{ */ /** @file * @author Markus Blatt * @brief Provides a class for building the galerkin product * based on a aggregation scheme. */ template struct OverlapVertex { /** * @brief The aggregate descriptor. */ typedef T Aggregate; /** * @brief The vertex descriptor. */ typedef T Vertex; /** * @brief The aggregate the vertex belongs to. */ Aggregate* aggregate; /** * @brief The vertex descriptor. */ Vertex vertex; }; /** * @brief Functor for building the sparsity pattern of the matrix * using examineConnectivity. */ template class SparsityBuilder { public: /** * @brief Constructor. * @param matrix The matrix whose sparsity pattern we * should set up. */ SparsityBuilder(M& matrix); void insert(const typename M::size_type& index); void operator++(); std::size_t minRowSize(); std::size_t maxRowSize(); std::size_t sumRowSize(); std::size_t index() { return row_.index(); } private: /** @brief Create iterator for the current row. */ typename M::CreateIterator row_; /** @brief The minim row size. */ std::size_t minRowSize_; /** @brief The maximum row size. */ std::size_t maxRowSize_; std::size_t sumRowSize_; #ifdef DUNE_ISTL_WITH_CHECKING bool diagonalInserted; #endif }; class BaseGalerkinProduct { public: /** * @brief Calculate the galerkin product. * @param fine The fine matrix. * @param aggregates The aggregate mapping. * @param coarse The coarse Matrix. * @param pinfo Parallel information about the fine level. * @param copy The attribute set identifying the copy nodes of the graph. */ template void calculate(const M& fine, const AggregatesMap& aggregates, M& coarse, const I& pinfo, const O& copy); }; template class GalerkinProduct : public BaseGalerkinProduct { public: typedef T ParallelInformation; /** * @brief Calculates the coarse matrix via a Galerkin product. * @param fineGraph The graph of the fine matrix. * @param visitedMap Map for marking vertices as visited. * @param pinfo Parallel information about the fine level. * @param aggregates The mapping of the fine level unknowns onto aggregates. * @param size The number of columns and rows of the coarse matrix. * @param copy The attribute set identifying the copy nodes of the graph. */ template typename G::MutableMatrix* build(G& fineGraph, V& visitedMap, const ParallelInformation& pinfo, AggregatesMap& aggregates, const typename G::Matrix::size_type& size, const Set& copy); private: /** * @brief Builds the data structure needed for rebuilding the aggregates int the overlap. * @param graph The graph of the matrix. * @param pinfo The parallel information. * @param aggregates The mapping onto the aggregates. */ template const OverlapVertex* buildOverlapVertices(const G& graph, const I& pinfo, AggregatesMap& aggregates, const Set& overlap, std::size_t& overlapCount); template struct OVLess { bool operator()(const OverlapVertex& o1, const OverlapVertex& o2) { return *o1.aggregate < *o2.aggregate; } }; }; template<> class GalerkinProduct : public BaseGalerkinProduct { public: /** * @brief Calculates the coarse matrix via a Galerkin product. * @param fineGraph The graph of the fine matrix. * @param visitedMap Map for marking vertices as visited. * @param pinfo Parallel information about the fine level. * @param aggregates The mapping of the fine level unknowns onto aggregates. * @param size The number of columns and rows of the coarse matrix. * @param copy The attribute set identifying the copy nodes of the graph. */ template typename G::MutableMatrix* build(G& fineGraph, V& visitedMap, const SequentialInformation& pinfo, const AggregatesMap& aggregates, const typename G::Matrix::size_type& size, const Set& copy); }; struct BaseConnectivityConstructor { template static void constructOverlapConnectivity(R& row, G& graph, V& visitedMap, const AggregatesMap& aggregates, const OverlapVertex*& seed, const OverlapVertex* overlapEnd); /** * @brief Construct the connectivity of an aggregate in the overlap. */ template static void constructNonOverlapConnectivity(R& row, G& graph, V& visitedMap, const AggregatesMap& aggregates, const typename G::VertexDescriptor& seed); /** * @brief Visitor for identifying connected aggregates during a breadthFirstSearch. */ template class ConnectedBuilder { public: /** * @brief The type of the graph. */ typedef G Graph; /** * @brief The constant edge iterator. */ typedef typename Graph::ConstEdgeIterator ConstEdgeIterator; /** * @brief The type of the connected set. */ typedef S Set; /** * @brief The type of the map for marking vertices as visited. */ typedef V VisitedMap; /** * @brief The vertex descriptor of the graph. */ typedef typename Graph::VertexDescriptor Vertex; /** * @brief Constructor * @param aggregates The mapping of the vertices onto the aggregates. * @param graph The graph to work on. * @param visitedMap The map for marking vertices as visited * @param connected The set to added the connected aggregates to. */ ConnectedBuilder(const AggregatesMap& aggregates, Graph& graph, VisitedMap& visitedMap, Set& connected); /** * @brief Process an edge pointing to another aggregate. * @param edge The iterator positioned at the edge. */ void operator()(const ConstEdgeIterator& edge); private: /** * @brief The mapping of the vertices onto the aggregates. */ const AggregatesMap& aggregates_; Graph& graph_; /** * @brief The map for marking vertices as visited. */ VisitedMap& visitedMap_; /** * @brief The set to add the connected aggregates to. */ Set& connected_; }; }; template struct ConnectivityConstructor : public BaseConnectivityConstructor { typedef typename G::VertexDescriptor Vertex; template static void examine(G& graph, V& visitedMap, const T& pinfo, const AggregatesMap& aggregates, const O& overlap, const OverlapVertex* overlapVertices, const OverlapVertex* overlapEnd, R& row); }; template struct ConnectivityConstructor : public BaseConnectivityConstructor { typedef typename G::VertexDescriptor Vertex; template static void examine(G& graph, V& visitedMap, const SequentialInformation& pinfo, const AggregatesMap& aggregates, R& row); }; template struct DirichletBoundarySetter { template static void set(M& coarse, const T& pinfo, const O& copy); }; template<> struct DirichletBoundarySetter { template static void set(M& coarse, const SequentialInformation& pinfo, const O& copy); }; template void BaseConnectivityConstructor::constructNonOverlapConnectivity(R& row, G& graph, V& visitedMap, const AggregatesMap& aggregates, const typename G::VertexDescriptor& seed) { assert(row.index()==aggregates[seed]); row.insert(aggregates[seed]); ConnectedBuilder conBuilder(aggregates, graph, visitedMap, row); typedef typename G::VertexDescriptor Vertex; typedef std::allocator Allocator; typedef SLList VertexList; typedef typename AggregatesMap::DummyEdgeVisitor DummyVisitor; VertexList vlist; DummyVisitor dummy; aggregates.template breadthFirstSearch(seed,aggregates[seed], graph, vlist, dummy, conBuilder, visitedMap); } template void BaseConnectivityConstructor::constructOverlapConnectivity(R& row, G& graph, V& visitedMap, const AggregatesMap& aggregates, const OverlapVertex*& seed, const OverlapVertex* overlapEnd) { ConnectedBuilder conBuilder(aggregates, graph, visitedMap, row); const typename G::VertexDescriptor aggregate=*seed->aggregate; if (row.index()==*seed->aggregate) { while(seed != overlapEnd && aggregate == *seed->aggregate) { row.insert(*seed->aggregate); // Walk over all neighbours and add them to the connected array. visitNeighbours(graph, seed->vertex, conBuilder); // Mark vertex as visited put(visitedMap, seed->vertex, true); ++seed; } } } template BaseConnectivityConstructor::ConnectedBuilder::ConnectedBuilder(const AggregatesMap& aggregates, Graph& graph, VisitedMap& visitedMap, Set& connected) : aggregates_(aggregates), graph_(graph), visitedMap_(visitedMap), connected_(connected) {} template void BaseConnectivityConstructor::ConnectedBuilder::operator()(const ConstEdgeIterator& edge) { const Vertex& vertex = aggregates_[edge.target()]; assert(vertex!= AggregatesMap::UNAGGREGATED); if(vertex!= AggregatesMap::ISOLATED) connected_.insert(vertex); } template template const OverlapVertex* GalerkinProduct::buildOverlapVertices(const G& graph, const I& pinfo, AggregatesMap& aggregates, const Set& overlap, std::size_t& overlapCount) { // count the overlap vertices. typedef typename G::ConstVertexIterator ConstIterator; typedef typename I::GlobalLookupIndexSet GlobalLookup; typedef typename GlobalLookup::IndexPair IndexPair; const ConstIterator end = graph.end(); overlapCount = 0; const GlobalLookup& lookup=pinfo.globalLookup(); for(ConstIterator vertex=graph.begin(); vertex != end; ++vertex) { const IndexPair* pair = lookup.pair(*vertex); if(pair!=0 && overlap.contains(pair->local().attribute())) ++overlapCount; } // Allocate space typedef typename G::VertexDescriptor Vertex; OverlapVertex* overlapVertices = new OverlapVertex[overlapCount=0 ? 1 : overlapCount]; if(overlapCount==0) return overlapVertices; // Initialize them overlapCount=0; for(ConstIterator vertex=graph.begin(); vertex != end; ++vertex) { const IndexPair* pair = lookup.pair(*vertex); if(pair!=0 && overlap.contains(pair->local().attribute())) { overlapVertices[overlapCount].aggregate = &aggregates[pair->local()]; overlapVertices[overlapCount].vertex = pair->local(); ++overlapCount; } } dverb << overlapCount<<" overlap vertices"<()); // due to the sorting the isolated aggregates (to be skipped) are at the end. return overlapVertices; } template template void ConnectivityConstructor::examine(G& graph, V& visitedMap, const T& pinfo, const AggregatesMap& aggregates, const O& overlap, const OverlapVertex* overlapVertices, const OverlapVertex* overlapEnd, R& row) { typedef typename T::GlobalLookupIndexSet GlobalLookup; const GlobalLookup& lookup = pinfo.globalLookup(); typedef typename G::VertexIterator VertexIterator; VertexIterator vend=graph.end(); #ifdef DUNE_ISTL_WITH_CHECKING std::set examined; #endif // The aggregates owned by the process have lower local indices // then those not owned. We process them in the first pass. // They represent the rows 0, 1, ..., n of the coarse matrix for(VertexIterator vertex = graph.begin(); vertex != vend; ++vertex) if(!get(visitedMap, *vertex)) { // In the first pass we only process owner nodes typedef typename GlobalLookup::IndexPair IndexPair; const IndexPair* pair = lookup.pair(*vertex); if(pair==0 || !overlap.contains(pair->local().attribute())) { #ifdef DUNE_ISTL_WITH_CHECKING assert(examined.find(aggregates[*vertex])==examined.end()); examined.insert(aggregates[*vertex]); #endif constructNonOverlapConnectivity(row, graph, visitedMap, aggregates, *vertex); // only needed for ALU // (ghosts with same global id as owners on the same process) if (SolverCategory::category(pinfo) == static_cast(SolverCategory::nonoverlapping)) { if(overlapVertices != overlapEnd) { if(*overlapVertices->aggregate!=AggregatesMap::ISOLATED) { constructOverlapConnectivity(row, graph, visitedMap, aggregates, overlapVertices, overlapEnd); } else{ ++overlapVertices; } } } ++row; } } dvverb<<"constructed "<aggregate!=AggregatesMap::ISOLATED) { #ifdef DUNE_ISTL_WITH_CHECKING typedef typename GlobalLookup::IndexPair IndexPair; const IndexPair* pair = lookup.pair(overlapVertices->vertex); assert(pair!=0 && overlap.contains(pair->local().attribute())); assert(examined.find(aggregates[overlapVertices->vertex])==examined.end()); examined.insert(aggregates[overlapVertices->vertex]); #endif constructOverlapConnectivity(row, graph, visitedMap, aggregates, overlapVertices, overlapEnd); ++row; }else{ ++overlapVertices; } } template template void ConnectivityConstructor::examine(G& graph, V& visitedMap, [[maybe_unused]] const SequentialInformation& pinfo, const AggregatesMap& aggregates, R& row) { typedef typename G::VertexIterator VertexIterator; VertexIterator vend=graph.end(); for(VertexIterator vertex = graph.begin(); vertex != vend; ++vertex) { if(!get(visitedMap, *vertex)) { constructNonOverlapConnectivity(row, graph, visitedMap, aggregates, *vertex); ++row; } } } template SparsityBuilder::SparsityBuilder(M& matrix) : row_(matrix.createbegin()), minRowSize_(std::numeric_limits::max()), maxRowSize_(0), sumRowSize_(0) { #ifdef DUNE_ISTL_WITH_CHECKING diagonalInserted = false; #endif } template std::size_t SparsityBuilder::maxRowSize() { return maxRowSize_; } template std::size_t SparsityBuilder::minRowSize() { return minRowSize_; } template std::size_t SparsityBuilder::sumRowSize() { return sumRowSize_; } template void SparsityBuilder::operator++() { sumRowSize_ += row_.size(); minRowSize_=std::min(minRowSize_, row_.size()); maxRowSize_=std::max(maxRowSize_, row_.size()); ++row_; #ifdef DUNE_ISTL_WITH_CHECKING assert(diagonalInserted); diagonalInserted = false; #endif } template void SparsityBuilder::insert(const typename M::size_type& index) { row_.insert(index); #ifdef DUNE_ISTL_WITH_CHECKING diagonalInserted = diagonalInserted || row_.index()==index; #endif } template template typename G::MutableMatrix* GalerkinProduct::build(G& fineGraph, V& visitedMap, const ParallelInformation& pinfo, AggregatesMap& aggregates, const typename G::Matrix::size_type& size, const Set& overlap) { typedef OverlapVertex OverlapVertex; std::size_t count; const OverlapVertex* overlapVertices = buildOverlapVertices(fineGraph, pinfo, aggregates, overlap, count); typedef typename G::MutableMatrix M; M* coarseMatrix = new M(size, size, M::row_wise); // Reset the visited flags of all vertices. // As the isolated nodes will be skipped we simply mark them as visited typedef typename G::VertexIterator Vertex; Vertex vend = fineGraph.end(); for(Vertex vertex = fineGraph.begin(); vertex != vend; ++vertex) { assert(aggregates[*vertex] != AggregatesMap::UNAGGREGATED); put(visitedMap, *vertex, aggregates[*vertex]==AggregatesMap::ISOLATED); } typedef typename G::MutableMatrix M; SparsityBuilder sparsityBuilder(*coarseMatrix); ConnectivityConstructor::examine(fineGraph, visitedMap, pinfo, aggregates, overlap, overlapVertices, overlapVertices+count, sparsityBuilder); dinfo<N()<<"x"<M()<<" row: min="<