// 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_AMG_MATRIXHIERARCHY_HH #define DUNE_AMG_MATRIXHIERARCHY_HH #include #include #include "aggregates.hh" #include "graph.hh" #include "galerkin.hh" #include "renumberer.hh" #include "graphcreator.hh" #include "hierarchy.hh" #include #include #include #include #include #include #include #include #include #include #include namespace Dune { namespace Amg { /** * @addtogroup ISTL_PAAMG * * @{ */ /** @file * @author Markus Blatt * @brief Provides a classes representing the hierarchies in AMG. */ enum { /** * @brief Hard limit for the number of processes allowed. * * This is needed to prevent overflows when calculating * the coarsening rate. Currently set 72,000 which is * enough for JUGENE. */ MAX_PROCESSES = 72000 }; /** * @brief The hierarchies build by the coarsening process. * * Namely a hierarchy of matrices, index sets, remote indices, * interfaces and communicators. */ template > class MatrixHierarchy { public: /** @brief The type of the matrix operator. */ typedef M MatrixOperator; /** @brief The type of the matrix. */ typedef typename MatrixOperator::matrix_type Matrix; /** @brief The type of the index set. */ typedef PI ParallelInformation; /** @brief The allocator to use. */ typedef A Allocator; /** @brief The type of the aggregates map we use. */ typedef Dune::Amg::AggregatesMap::VertexDescriptor> AggregatesMap; /** @brief The type of the parallel matrix hierarchy. */ typedef Dune::Amg::Hierarchy ParallelMatrixHierarchy; /** @brief The type of the parallel informarion hierarchy. */ typedef Dune::Amg::Hierarchy ParallelInformationHierarchy; /** @brief Allocator for pointers. */ using AAllocator = typename std::allocator_traits::template rebind_alloc; /** @brief The type of the aggregates maps list. */ typedef std::list AggregatesMapList; /** @brief The type of the redistribute information. */ typedef RedistributeInformation RedistributeInfoType; /** @brief Allocator for RedistributeInfoType. */ using RILAllocator = typename std::allocator_traits::template rebind_alloc; /** @brief The type of the list of redistribute information. */ typedef std::list RedistributeInfoList; /** * @brief Constructor * @param fineMatrix The matrix to coarsen. * @param pinfo The information about the parallel data decomposition at the first level. */ MatrixHierarchy(std::shared_ptr fineMatrix, std::shared_ptr pinfo = std::make_shared()); ~MatrixHierarchy(); /** * @brief Build the matrix hierarchy using aggregation. * * @brief criterion The criterion describing the aggregation process. */ template void build(const T& criterion); /** * @brief Recalculate the galerkin products. * * If the data of the fine matrix changes but not its sparsity pattern * this will recalculate all coarser levels without starting the expensive * aggregation process all over again. */ template void recalculateGalerkin(const F& copyFlags); /** * @brief Coarsen the vector hierarchy according to the matrix hierarchy. * @param hierarchy The vector hierarchy to coarsen. */ template void coarsenVector(Hierarchy, TA>& hierarchy) const; /** * @brief Coarsen the smoother hierarchy according to the matrix hierarchy. * @param smoothers The smoother hierarchy to coarsen. * @param args The arguments for the construction of the coarse level smoothers. */ template void coarsenSmoother(Hierarchy& smoothers, const typename SmootherTraits::Arguments& args) const; /** * @brief Get the number of levels in the hierarchy. * @return The number of levels. */ std::size_t levels() const; /** * @brief Get the max number of levels in the hierarchy of processors. * @return The maximum number of levels. */ std::size_t maxlevels() const; bool hasCoarsest() const; /** * @brief Whether the hierarchy was built. * @return true if the MatrixHierarchy::build method was called. */ bool isBuilt() const; /** * @brief Get the matrix hierarchy. * @return The matrix hierarchy. */ const ParallelMatrixHierarchy& matrices() const; /** * @brief Get the hierarchy of the parallel data distribution information. * @return The hierarchy of the parallel data distribution information. */ const ParallelInformationHierarchy& parallelInformation() const; /** * @brief Get the hierarchy of the mappings of the nodes onto aggregates. * @return The hierarchy of the mappings of the nodes onto aggregates. */ const AggregatesMapList& aggregatesMaps() const; /** * @brief Get the hierarchy of the information about redistributions, * @return The hierarchy of the information about redistributions of the * data to fewer processes. */ const RedistributeInfoList& redistributeInformation() const; double getProlongationDampingFactor() const { return prolongDamp_; } /** * @brief Get the mapping of fine level unknowns to coarse level * aggregates. * * For each fine level unknown i the corresponding data[i] is the * aggregate it belongs to on the coarsest level. * * @param[out] data The mapping of fine level unknowns to coarse level * aggregates. */ void getCoarsestAggregatesOnFinest(std::vector& data) const; private: typedef typename ConstructionTraits::Arguments MatrixArgs; typedef typename ConstructionTraits::Arguments CommunicationArgs; /** @brief The list of aggregates maps. */ AggregatesMapList aggregatesMaps_; /** @brief The list of redistributes. */ RedistributeInfoList redistributes_; /** @brief The hierarchy of parallel matrices. */ ParallelMatrixHierarchy matrices_; /** @brief The hierarchy of the parallel information. */ ParallelInformationHierarchy parallelInformation_; /** @brief Whether the hierarchy was built. */ bool built_; /** @brief The maximum number of level across all processors.*/ int maxlevels_; double prolongDamp_; /** * @brief functor to print matrix statistics. */ template struct MatrixStats { /** * @brief Print matrix statistics. */ static void stats([[maybe_unused]] const Matrix& matrix) {} }; template struct MatrixStats { struct calc { typedef typename Matrix::size_type size_type; typedef typename Matrix::row_type matrix_row; calc() { min=std::numeric_limits::max(); max=0; sum=0; } void operator()(const matrix_row& row) { min=std::min(min, row.size()); max=std::max(max, row.size()); sum += row.size(); } size_type min; size_type max; size_type sum; }; /** * @brief Print matrix statistics. */ static void stats(const Matrix& matrix) { calc c= for_each(matrix.begin(), matrix.end(), calc()); dinfo<<"Matrix row: min="< bool repartitionAndDistributeMatrix(const M& origMatrix, std::shared_ptr newMatrix, C& origComm, std::shared_ptr& newComm, RedistributeInformation& ri, int nparts, C1& criterion) { Timer time; #ifdef AMG_REPART_ON_COMM_GRAPH // Done not repartition the matrix graph, but a graph of the communication scheme. bool existentOnRedist=Dune::commGraphRepartition(origMatrix, origComm, nparts, newComm, ri.getInterface(), criterion.debugLevel()>1); #else typedef Dune::Amg::MatrixGraph MatrixGraph; typedef Dune::Amg::PropertiesGraph PropertiesGraph; MatrixGraph graph(origMatrix); PropertiesGraph pgraph(graph); buildDependency(pgraph, origMatrix, criterion, false); #ifdef DEBUG_REPART if(origComm.communicator().rank()==0) std::cout<<"Original matrix"<1); #endif // if else AMG_REPART if(origComm.communicator().rank()==0 && criterion.debugLevel()>1) std::cout<<"Repartitioning took "<indexSet(), origComm.communicator()); #endif redistributeMatrix(const_cast(origMatrix), *newMatrix, origComm, *newComm, ri); #ifdef DEBUG_REPART if(origComm.communicator().rank()==0) std::cout<<"Original matrix"<communicator().size()>0) printGlobalSparseMatrix(*newMatrix, *newComm, std::cout); origComm.communicator().barrier(); #endif if(origComm.communicator().rank()==0 && criterion.debugLevel()>1) std::cout<<"Redistributing matrix took "< MatrixHierarchy::MatrixHierarchy(std::shared_ptr fineMatrix, std::shared_ptr pinfo) : matrices_(fineMatrix), parallelInformation_(pinfo) { if (SolverCategory::category(*fineMatrix) != SolverCategory::category(*pinfo)) DUNE_THROW(ISTLError, "MatrixOperator and ParallelInformation must belong to the same category!"); } template template void MatrixHierarchy::build(const T& criterion) { prolongDamp_ = criterion.getProlongationDampingFactor(); typedef O OverlapFlags; typedef typename ParallelMatrixHierarchy::Iterator MatIterator; typedef typename ParallelInformationHierarchy::Iterator PInfoIterator; static const int noints=(Dune::Amg::MAX_PROCESSES/4096>0) ? (Dune::Amg::MAX_PROCESSES/4096) : 1; typedef bigunsignedint BIGINT; GalerkinProduct productBuilder; MatIterator mlevel = matrices_.finest(); MatrixStats::stats(mlevel->getmat()); PInfoIterator infoLevel = parallelInformation_.finest(); BIGINT finenonzeros=countNonZeros(mlevel->getmat()); finenonzeros = infoLevel->communicator().sum(finenonzeros); BIGINT allnonzeros = finenonzeros; int level = 0; int rank = 0; BIGINT unknowns = mlevel->getmat().N(); unknowns = infoLevel->communicator().sum(unknowns); double dunknowns=unknowns.todouble(); infoLevel->buildGlobalLookup(mlevel->getmat().N()); redistributes_.push_back(RedistributeInfoType()); for(; level < criterion.maxLevel(); ++level, ++mlevel) { assert(matrices_.levels()==redistributes_.size()); rank = infoLevel->communicator().rank(); if(rank==0 && criterion.debugLevel()>1) std::cout<<"Level "<communicator().size() <<" unknowns per proc (procs="<communicator().size()<<")"<communicator().size())) && infoLevel->communicator().size()>1 && dunknowns/infoLevel->communicator().size() <= criterion.coarsenTarget()) { // accumulate to fewer processors std::shared_ptr redistMat = std::make_shared(); std::shared_ptr redistComm; std::size_t nodomains = (std::size_t)std::ceil(dunknowns/(criterion.minAggregateSize() *criterion.coarsenTarget())); if( nodomains<=criterion.minAggregateSize()/2 || dunknowns <= criterion.coarsenTarget() ) nodomains=1; bool existentOnNextLevel = repartitionAndDistributeMatrix(mlevel->getmat(), redistMat, *infoLevel, redistComm, redistributes_.back(), nodomains, criterion); BIGINT unknownsRedist = redistMat->N(); unknownsRedist = infoLevel->communicator().sum(unknownsRedist); dunknowns= unknownsRedist.todouble(); if(redistComm->communicator().rank()==0 && criterion.debugLevel()>1) std::cout<<"Level "<communicator().size() <<" unknowns per proc (procs="<communicator().size()<<")"<::construct(args)); assert(mlevel.isRedistributed()); infoLevel.addRedistributed(redistComm); infoLevel->freeGlobalLookup(); if(!existentOnNextLevel) // We do not hold any data on the redistributed partitioning break; // Work on the redistributed Matrix from now on matrix = &(mlevel.getRedistributed()); info = &(infoLevel.getRedistributed()); info->buildGlobalLookup(matrix->getmat().N()); } rank = info->communicator().rank(); if(dunknowns <= criterion.coarsenTarget()) // No further coarsening needed break; typedef PropertiesGraphCreator GraphCreator; typedef typename GraphCreator::PropertiesGraph PropertiesGraph; typedef typename GraphCreator::GraphTuple GraphTuple; typedef typename PropertiesGraph::VertexDescriptor Vertex; std::vector excluded(matrix->getmat().N(), false); GraphTuple graphs = GraphCreator::create(*matrix, excluded, *info, OverlapFlags()); AggregatesMap* aggregatesMap=new AggregatesMap(std::get<1>(graphs)->maxVertex()+1); aggregatesMaps_.push_back(aggregatesMap); Timer watch; watch.reset(); auto [noAggregates, isoAggregates, oneAggregates, skippedAggregates] = aggregatesMap->buildAggregates(matrix->getmat(), *(std::get<1>(graphs)), criterion, level==0); if(rank==0 && criterion.debugLevel()>2) std::cout<<" Have built "<communicator().rank(); int n = UNKNOWNS/procs; // number of unknowns per process int bigger = UNKNOWNS%procs; // number of process with n+1 unknowns // Compute owner region if(rank0) overlapStart = start - 1; else overlapStart = start; if(endnoVertices()); for(int j=0; j< UNKNOWNS; ++j) for(int i=0; i < UNKNOWNS; ++i) { if(i>=overlapStart && i1 && info->communicator().rank()==0) std::cout<<"aggregating finished."<communicator().sum(gnoAggregates); double dgnoAggregates = gnoAggregates.todouble(); #ifdef TEST_AGGLO BIGINT gnoAggregates=((UNKNOWNS)/2)*((UNKNOWNS)/2); #endif if(criterion.debugLevel()>2 && rank==0) std::cout << "Building "<0) std::cerr << "Stopped coarsening because of rate breakdown "<free(); delete aggregatesMap; aggregatesMaps_.pop_back(); if(criterion.accumulate() && mlevel.isRedistributed() && info->communicator().size()>1) { // coarse level matrix was already redistributed, but to more than 1 process // Therefore need to delete the redistribution. Further down it will // then be redistributed to 1 process delete &(mlevel.getRedistributed().getmat()); mlevel.deleteRedistributed(); delete &(infoLevel.getRedistributed()); infoLevel.deleteRedistributed(); redistributes_.back().resetSetup(); } break; } unknowns = noAggregates; dunknowns = dgnoAggregates; CommunicationArgs commargs(info->communicator(),info->category()); parallelInformation_.addCoarser(commargs); ++infoLevel; // parallel information on coarse level typename PropertyMapTypeSelector::Type visitedMap = get(VertexVisitedTag(), *(std::get<1>(graphs))); watch.reset(); int aggregates = IndicesCoarsener ::coarsen(*info, *(std::get<1>(graphs)), visitedMap, *aggregatesMap, *infoLevel, noAggregates, criterion.useFixedOrder()); GraphCreator::free(graphs); if(criterion.debugLevel()>2) { if(rank==0) std::cout<<"Coarsening of index sets took "<buildGlobalLookup(aggregates); AggregatesPublisher::publish(*aggregatesMap, *info, infoLevel->globalLookup()); if(criterion.debugLevel()>2) { if(rank==0) std::cout<<"Communicating global aggregate numbers took "<& visited=excluded; typedef std::vector::iterator Iterator; typedef IteratorPropertyMap VisitedMap2; Iterator end = visited.end(); for(Iterator iter= visited.begin(); iter != end; ++iter) *iter=false; VisitedMap2 visitedMap2(visited.begin(), Dune::IdentityMap()); std::shared_ptr coarseMatrix(productBuilder.build(*(std::get<0>(graphs)), visitedMap2, *info, *aggregatesMap, aggregates, OverlapFlags())); dverb<<"Building of sparsity pattern took "<freeGlobalLookup(); delete std::get<0>(graphs); productBuilder.calculate(matrix->getmat(), *aggregatesMap, *coarseMatrix, *infoLevel, OverlapFlags()); if(criterion.debugLevel()>2) { if(rank==0) std::cout<<"Calculation entries of Galerkin product took "<communicator().sum(nonzeros); MatrixArgs args(coarseMatrix, *infoLevel); matrices_.addCoarser(args); redistributes_.push_back(RedistributeInfoType()); } // end level loop infoLevel->freeGlobalLookup(); built_=true; AggregatesMap* aggregatesMap=new AggregatesMap(0); aggregatesMaps_.push_back(aggregatesMap); if(criterion.debugLevel()>0) { if(level==criterion.maxLevel()) { BIGINT unknownsLevel = mlevel->getmat().N(); unknownsLevel = infoLevel->communicator().sum(unknownsLevel); if(rank==0 && criterion.debugLevel()>1) { double dunknownsLevel = unknownsLevel.todouble(); std::cout<<"Level "<communicator().size() <<" unknowns per proc (procs="<communicator().size()<<")"<communicator().size()>1) { #if HAVE_MPI && !HAVE_PARMETIS if(criterion.accumulate()==successiveAccu && infoLevel->communicator().rank()==0) std::cerr<<"Successive accumulation of data on coarse levels only works with ParMETIS installed." <<" Fell back to accumulation to one domain on coarsest level"< redistMat = std::make_shared(); std::shared_ptr redistComm; int nodomains = 1; repartitionAndDistributeMatrix(mlevel->getmat(), redistMat, *infoLevel, redistComm, redistributes_.back(), nodomains,criterion); MatrixArgs args(redistMat, *redistComm); BIGINT unknownsRedist = redistMat->N(); unknownsRedist = infoLevel->communicator().sum(unknownsRedist); if(redistComm->communicator().rank()==0 && criterion.debugLevel()>1) { double dunknownsRedist = unknownsRedist.todouble(); std::cout<<"Level "<communicator().size() <<" unknowns per proc (procs="<communicator().size()<<")"<::construct(args)); infoLevel.addRedistributed(redistComm); infoLevel->freeGlobalLookup(); } int levels = matrices_.levels(); maxlevels_ = parallelInformation_.finest()->communicator().max(levels); assert(matrices_.levels()==redistributes_.size()); if(hasCoarsest() && rank==0 && criterion.debugLevel()>1) std::cout<<"operator complexity: "< const typename MatrixHierarchy::ParallelMatrixHierarchy& MatrixHierarchy::matrices() const { return matrices_; } template const typename MatrixHierarchy::ParallelInformationHierarchy& MatrixHierarchy::parallelInformation() const { return parallelInformation_; } template void MatrixHierarchy::getCoarsestAggregatesOnFinest(std::vector& data) const { int levels=aggregatesMaps().size(); int maxlevels=parallelInformation_.finest()->communicator().max(levels); std::size_t size=(*(aggregatesMaps().begin()))->noVertices(); // We need an auxiliary vector for the consecutive prolongation. std::vector tmp; std::vector *coarse, *fine; // make sure the allocated space suffices. tmp.reserve(size); data.reserve(size); // Correctly assign coarse and fine for the first prolongation such that // we end up in data in the end. if(levels%2==0) { coarse=&tmp; fine=&data; }else{ coarse=&data; fine=&tmp; } // Number the unknowns on the coarsest level consecutively for each process. if(levels==maxlevels) { const AggregatesMap& map = *(*(++aggregatesMaps().rbegin())); std::size_t m=0; for(typename AggregatesMap::const_iterator iter = map.begin(); iter != map.end(); ++iter) if(*iter< AggregatesMap::ISOLATED) m=std::max(*iter,m); coarse->resize(m+1); std::size_t i=0; srand((unsigned)std::clock()); std::set used; for(typename std::vector::iterator iter=coarse->begin(); iter != coarse->end(); ++iter, ++i) { std::pair::iterator,bool> ibpair = used.insert(static_cast((((double)rand())/(RAND_MAX+1.0)))*coarse->size()); while(!ibpair.second) ibpair = used.insert(static_cast((((double)rand())/(RAND_MAX+1.0))*coarse->size())); *iter=*(ibpair.first); } } typename ParallelInformationHierarchy::Iterator pinfo = parallelInformation().coarsest(); --pinfo; // Now consecutively project the numbers to the finest level. for(typename AggregatesMapList::const_reverse_iterator aggregates=++aggregatesMaps().rbegin(); aggregates != aggregatesMaps().rend(); ++aggregates,--levels) { fine->resize((*aggregates)->noVertices()); fine->assign(fine->size(), 0); Transfer, ParallelInformation> ::prolongateVector(*(*aggregates), *coarse, *fine, static_cast(1), *pinfo); --pinfo; std::swap(coarse, fine); } // Assertion to check that we really projected to data on the last step. assert(coarse==&data); } template const typename MatrixHierarchy::AggregatesMapList& MatrixHierarchy::aggregatesMaps() const { return aggregatesMaps_; } template const typename MatrixHierarchy::RedistributeInfoList& MatrixHierarchy::redistributeInformation() const { return redistributes_; } template MatrixHierarchy::~MatrixHierarchy() { typedef typename AggregatesMapList::reverse_iterator AggregatesMapIterator; typedef typename ParallelMatrixHierarchy::Iterator Iterator; typedef typename ParallelInformationHierarchy::Iterator InfoIterator; AggregatesMapIterator amap = aggregatesMaps_.rbegin(); InfoIterator info = parallelInformation_.coarsest(); for(Iterator level=matrices_.coarsest(), finest=matrices_.finest(); level != finest; --level, --info, ++amap) { (*amap)->free(); delete *amap; } delete *amap; } template template void MatrixHierarchy::coarsenVector(Hierarchy, TA>& hierarchy) const { assert(hierarchy.levels()==1); typedef typename ParallelMatrixHierarchy::ConstIterator Iterator; typedef typename RedistributeInfoList::const_iterator RIter; RIter redist = redistributes_.begin(); Iterator matrix = matrices_.finest(), coarsest = matrices_.coarsest(); int level=0; if(redist->isSetup()) hierarchy.addRedistributedOnCoarsest(matrix.getRedistributed().getmat().N()); Dune::dvverb<<"Level "<getmat().N()<<" unknowns!"<getmat().N()<<" unknowns!"<getmat().N()); if(redist->isSetup()) hierarchy.addRedistributedOnCoarsest(matrix.getRedistributed().getmat().N()); } } template template void MatrixHierarchy::coarsenSmoother(Hierarchy& smoothers, const typename SmootherTraits::Arguments& sargs) const { assert(smoothers.levels()==0); typedef typename ParallelMatrixHierarchy::ConstIterator MatrixIterator; typedef typename ParallelInformationHierarchy::ConstIterator PinfoIterator; typedef typename AggregatesMapList::const_iterator AggregatesIterator; typename ConstructionTraits::Arguments cargs; cargs.setArgs(sargs); PinfoIterator pinfo = parallelInformation_.finest(); AggregatesIterator aggregates = aggregatesMaps_.begin(); int level=0; for(MatrixIterator matrix = matrices_.finest(), coarsest = matrices_.coarsest(); matrix != coarsest; ++matrix, ++pinfo, ++aggregates, ++level) { cargs.setMatrix(matrix->getmat(), **aggregates); cargs.setComm(*pinfo); smoothers.addCoarser(cargs); } if(maxlevels()>levels()) { // This is not the globally coarsest level and therefore smoothing is needed cargs.setMatrix(matrices_.coarsest()->getmat(), **aggregates); cargs.setComm(*pinfo); smoothers.addCoarser(cargs); ++level; } } template template void MatrixHierarchy::recalculateGalerkin(const F& copyFlags) { typedef typename AggregatesMapList::iterator AggregatesMapIterator; typedef typename ParallelMatrixHierarchy::Iterator Iterator; typedef typename ParallelInformationHierarchy::Iterator InfoIterator; AggregatesMapIterator amap = aggregatesMaps_.begin(); BaseGalerkinProduct productBuilder; InfoIterator info = parallelInformation_.finest(); typename RedistributeInfoList::iterator riIter = redistributes_.begin(); Iterator level = matrices_.finest(), coarsest=matrices_.coarsest(); if(level.isRedistributed()) { info->buildGlobalLookup(level->getmat().N()); redistributeMatrixEntries(const_cast(level->getmat()), const_cast(level.getRedistributed().getmat()), *info,info.getRedistributed(), *riIter); info->freeGlobalLookup(); } for(; level!=coarsest; ++amap) { const Matrix& fine = (level.isRedistributed() ? level.getRedistributed() : *level).getmat(); ++level; ++info; ++riIter; productBuilder.calculate(fine, *(*amap), const_cast(level->getmat()), *info, copyFlags); if(level.isRedistributed()) { info->buildGlobalLookup(level->getmat().N()); redistributeMatrixEntries(const_cast(level->getmat()), const_cast(level.getRedistributed().getmat()), *info, info.getRedistributed(), *riIter); info->freeGlobalLookup(); } } } template std::size_t MatrixHierarchy::levels() const { return matrices_.levels(); } template std::size_t MatrixHierarchy::maxlevels() const { return maxlevels_; } template bool MatrixHierarchy::hasCoarsest() const { return levels()==maxlevels() && (!matrices_.coarsest().isRedistributed() ||matrices_.coarsest()->getmat().N()>0); } template bool MatrixHierarchy::isBuilt() const { return built_; } /** @} */ } // namespace Amg } // namespace Dune #endif // end DUNE_AMG_MATRIXHIERARCHY_HH