MueLu  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node > Class Template Reference

#include <MueLu_LeftoverAggregationAlgorithm_decl.hpp>

Inheritance diagram for MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >:
MueLu::BaseClass MueLu::VerboseObject MueLu::Describable Teuchos::VerboseObject< VerboseObject > Teuchos::Describable Teuchos::VerboseObjectBase Teuchos::LabeledObject

Private Types

typedef GO global_size_t
 
typedef LO my_size_t
 

Private Attributes

double phase3AggCreation_
 
int minNodesPerAggregate_
 

Constructors/Destructors.

 LeftoverAggregationAlgorithm ()
 Constructor. More...
 
virtual ~LeftoverAggregationAlgorithm ()
 Destructor. More...
 

Set/get methods.

void SetMinNodesPerAggregate (int minNodesPerAggregate)
 
void SetPhase3AggCreation (double phase3AggCreation)
 
double GetPhase3AggCreation () const
 
int GetMinNodesPerAggregate () const
 

Aggregation methods.

void AggregateLeftovers (GraphBase const &graph, Aggregates &aggregates) const
 Take a partially aggregated graph and complete the aggregation. More...
 

Utilities

void RootCandidates (my_size_t nVertices, ArrayView< const LO > &vertex2AggId, GraphBase const &graph, ArrayRCP< LO > &candidates, my_size_t &nCandidates, global_size_t &nCandidatesGlobal) const
 Build a list of candidate root nodes. More...
 
int RemoveSmallAggs (Aggregates &aggregates, int min_size, RCP< Xpetra::Vector< double, LO, GO, NO > > &distWeights, const MueLu::CoupledAggregationCommHelper< LO, GO, NO > &myWidget) const
 Attempt to clean up aggregates that are too small. More...
 

Additional Inherited Members

- Public Member Functions inherited from MueLu::BaseClass
virtual ~BaseClass ()
 Destructor. More...
 
- Public Member Functions inherited from MueLu::VerboseObject
VerbLevel GetVerbLevel () const
 Get the verbosity level. More...
 
void SetVerbLevel (const VerbLevel verbLevel)
 Set the verbosity level of this object. More...
 
int GetProcRankVerbose () const
 Get proc rank used for printing. Do not use this information for any other purpose. More...
 
int SetProcRankVerbose (int procRank) const
 Set proc rank used for printing. More...
 
bool IsPrint (MsgType type, int thisProcRankOnly=-1) const
 Find out whether we need to print out information for a specific message type. More...
 
Teuchos::FancyOStreamGetOStream (MsgType type, int thisProcRankOnly=0) const
 Get an output stream for outputting the input message type. More...
 
Teuchos::FancyOStreamGetBlackHole () const
 
 VerboseObject ()
 
virtual ~VerboseObject ()
 Destructor. More...
 
- Public Member Functions inherited from Teuchos::VerboseObject< VerboseObject >
 VerboseObject (const EVerbosityLevel verbLevel=VERB_DEFAULT, const RCP< FancyOStream > &oStream=Teuchos::null)
 
virtual const VerboseObjectsetVerbLevel (const EVerbosityLevel verbLevel) const
 
virtual const VerboseObjectsetOverridingVerbLevel (const EVerbosityLevel verbLevel) const
 
virtual EVerbosityLevel getVerbLevel () const
 
TEUCHOSPARAMETERLIST_LIB_DLL_EXPORT
RCP< const ParameterList
getValidVerboseObjectSublist ()
 
TEUCHOSPARAMETERLIST_LIB_DLL_EXPORT
void 
setupVerboseObjectSublist (ParameterList *paramList)
 
TEUCHOSPARAMETERLIST_LIB_DLL_EXPORT
void 
readVerboseObjectSublist (ParameterList *paramList, RCP< FancyOStream > *oStream, EVerbosityLevel *verbLevel)
 
void readVerboseObjectSublist (ParameterList *paramList, VerboseObject< ObjectType > *verboseObject)
 
- Public Member Functions inherited from Teuchos::VerboseObjectBase
virtual ~VerboseObjectBase ()
 
 VerboseObjectBase (const RCP< FancyOStream > &oStream=Teuchos::null)
 
virtual const VerboseObjectBasesetOStream (const RCP< FancyOStream > &oStream) const
 
virtual const VerboseObjectBasesetOverridingOStream (const RCP< FancyOStream > &oStream) const
 
virtual VerboseObjectBasesetLinePrefix (const std::string &linePrefix)
 
virtual RCP< FancyOStreamgetOStream () const
 
virtual RCP< FancyOStreamgetOverridingOStream () const
 
virtual std::string getLinePrefix () const
 
virtual OSTab getOSTab (const int tabs=1, const std::string &linePrefix="") const
 
- Public Member Functions inherited from MueLu::Describable
virtual ~Describable ()
 Destructor. More...
 
virtual std::string ShortClassName () const
 Return the class name of the object, without template parameters and without namespace. More...
 
virtual void describe (Teuchos::FancyOStream &out_arg, const VerbLevel verbLevel=Default) const
 
virtual std::string description () const
 Return a simple one-line description of this object. More...
 
void describe (Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const
 Print the object with some verbosity level to an FancyOStream object. More...
 
- Public Member Functions inherited from Teuchos::Describable
void describe (std::ostream &out, const EVerbosityLevel verbLevel=verbLevel_default) const
 
 LabeledObject ()
 
virtual ~LabeledObject ()
 
virtual void setObjectLabel (const std::string &objectLabel)
 
virtual std::string getObjectLabel () const
 
DescribableStreamManipulatorState describe (const Describable &describable, const EVerbosityLevel verbLevel=Describable::verbLevel_default)
 
std::ostream & operator<< (std::ostream &os, const DescribableStreamManipulatorState &d)
 
- Static Public Member Functions inherited from MueLu::VerboseObject
static void SetMueLuOStream (const Teuchos::RCP< Teuchos::FancyOStream > &mueluOStream)
 
static Teuchos::RCP
< Teuchos::FancyOStream
GetMueLuOStream ()
 
static void SetDefaultVerbLevel (const VerbLevel defaultVerbLevel)
 Set the default (global) verbosity level. More...
 
static VerbLevel GetDefaultVerbLevel ()
 Get the default (global) verbosity level. More...
 
- Static Public Member Functions inherited from Teuchos::VerboseObject< VerboseObject >
static void setDefaultVerbLevel (const EVerbosityLevel defaultVerbLevel)
 
static EVerbosityLevel getDefaultVerbLevel ()
 
- Static Public Member Functions inherited from Teuchos::VerboseObjectBase
static void setDefaultOStream (const RCP< FancyOStream > &defaultOStream)
 
static RCP< FancyOStreamgetDefaultOStream ()
 
- Static Public Attributes inherited from Teuchos::Describable
static const EVerbosityLevel verbLevel_default
 
- Protected Member Functions inherited from Teuchos::VerboseObject< VerboseObject >
void initializeVerboseObject (const EVerbosityLevel verbLevel=VERB_DEFAULT, const RCP< FancyOStream > &oStream=Teuchos::null)
 
- Protected Member Functions inherited from Teuchos::VerboseObjectBase
void initializeVerboseObjectBase (const RCP< FancyOStream > &oStream=Teuchos::null)
 
virtual void informUpdatedVerbosityState () const
 

Detailed Description

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
class MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >

Definition at line 64 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

Member Typedef Documentation

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
typedef GO MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::global_size_t
private

Definition at line 68 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
typedef LO MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::my_size_t
private

Definition at line 69 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

Constructor & Destructor Documentation

template<class LocalOrdinal , class GlobalOrdinal , class Node >
MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::LeftoverAggregationAlgorithm ( )

Constructor.

Definition at line 65 of file MueLu_LeftoverAggregationAlgorithm_def.hpp.

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
virtual MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::~LeftoverAggregationAlgorithm ( )
inlinevirtual

Destructor.

Definition at line 80 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

Member Function Documentation

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
void MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::SetMinNodesPerAggregate ( int  minNodesPerAggregate)
inline

Definition at line 87 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
void MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::SetPhase3AggCreation ( double  phase3AggCreation)
inline

Definition at line 88 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
double MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::GetPhase3AggCreation ( ) const
inline

Definition at line 90 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
int MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::GetMinNodesPerAggregate ( ) const
inline

Definition at line 91 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

template<class LocalOrdinal , class GlobalOrdinal , class Node >
void MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::AggregateLeftovers ( GraphBase const &  graph,
Aggregates aggregates 
) const

Take a partially aggregated graph and complete the aggregation.

This is typically needed to take care of vertices that are left over after creating a bunch of ideal aggregates (root plus immediate neighbors).

On input, the structure Aggregates describes already aggregated vertices. The field procWinners[] indicates the processor owning the aggregate to which a vertex is "definitively" assigned. If on entry procWinners[i] == MUELU_UNASSIGNED, ArbitrateAndCommunicate() will arbitrate and decide which processor's aggregate really has the vertex. If only one processor claims ownership (as in the Uncoupled case), no real arbitration is needed. Otherwise, random arbitration is done.

This cleanup has many phases:

  • Phase 1b: Invoke ArbitrateAndCommunicate() to ensure that all processors have the same view of aggregated vertices (e.g., to which aggregate they have been assigned and which processor owns that aggregate).
  • Phase 2: Check for vertices (local or nonlocal) which are Adjacent to root nodes. Tentatively assign these to the aggregate associated with the root. Arbitrate any cases where several processors claim the same vertex for one of their aggregates via ArbitrateAndCommunicate().

Phase 3: Try to create new aggregates if it looks like there are root node candidates which have many unaggregated neighbors. This decision to make a new aggregate is based on only local information. However, the new aggregate will be tentatively assigned any unaggregated ghost vertices. Arbitration is again done by ArbitrateAndCommunicate() where local vertices use a weight[] = 2 and ghost vertices have weight[] = 1. The basic idea is that after arbitration, each aggregate is guaranteed to keep all local vertices assigned in this phase. Thus, by basing the aggregation creation logic on local information, we are guaranteed to have a sufficiently large aggregation. The only local vertices that might be assigned to another processor's aggregates are unclaimed during this phase of the aggregation.

  • Phase 4: EXPERIMENTAL
  • Phase 5: Sweep new points into existing aggregates. Each processor tries to assign any (whether it is a ghost or local) unaggregated vertex that it has to an aggregate that it owns. In other words, processor p attempts to assign vertex \(v\) to aggregate \(y\) where \(y\) is owned by p but \(v\) may be a ghost vertex (and so really assigned to another processor). Deciding which aggregate a vertex is assigned to is done by scoring. Roughly, we want
    • larger scores for \(y\) if \(v\) is close (graph distance) to \(y\)'s root.
    • larger scores for \(y\) if \(v\) has direct connections to several different vertices already assigned to \(y\).
    • lower scores for \(y\) if several vertices have already been swept into \(y\) during this phase.

Some care must be taken for vertices that are shared (either local vertices that are sent to other processors or ghost vertices) in that each processor sharing the vertex will attempt to assign it to different aggregates. ArbitrateAndCommunicate() is again used for arbitration with the score being given as the weight.

The main tricky thing occurs when \(v\) is tentatively added to \(y\). When assigning \(v'\) to \(y\), the assumed connection with \(v\) should not be the sole basis of this decision if there is some chance that \(v\) might be lost in arbitration. This could actually lead to \(v'\) being disconnected from the rest of the aggregate. This is by building a list of shared ids and checking that there is at least one vertex in the scoring that is either not shared or has already been definitively assigned to this processor's aggregate (i.e. have been assigned to a local aggregate and have been through arbitration).

Scoring is done by first giving a mark to vertices that have been already been assigned to aggregates. This mark essentially reflects the distance of this point to the root. Specifically,

\[ mark(v) \leftarrow MUELU\_DISTONE\_VERTEX\_WEIGHT \]

if \(v\) was assigned to an aggregate prior to this phase,

\[ mark(v) \leftarrow max(mark(v_k))/2 \]

otherwise, where \(max(mark(v_k))\) considers all vertices definitively assigned to \(y\) that have direct connections to \(v\).

Finally,

\[ score(\tilde{v},y) \leftarrow \Sigma(mark(\hat{v}_k)) - AggregateIncrementPenalty \]

where \(\tilde{v}\) is an unaggregated vertex being considered for assignment in aggregate \(y\) and \(hat{v}_k\) are all vertices in \(y\) with a direct connection to \(\tilde{v}\). AggregateIncrementPenalty is equal to

\[ \max (\mbox{INCR_SCALING}*NNewVtx, \Sigma(mark(\hat{v}_k))*(1-\mbox{MUELU_PENALTYFACTOR})) \]

where \( NNewVtx \) is the number of phase 5 vertices already assigned to \(y\).

One last wrinkle, is that we have wrapped the whole scoring/assigning of vertices inside a big loop that looks something like

for ( Threshold = big; Threshold >= 0; Reduce(Threshold));

New vertices are swept into aggregates only if their best score is >= a Threshold. This encourages only very good vertices to be assigned first followed by somewhat less well connected ones in later iterations of the loop. It also helps minimize the number of exclusions that would occur to address the issue mentioned above where we don't want to make assignment decisions based on connections to vertices that might be later lost in arbitration.

  • Phase 6: Aggregate remaining vertices and avoid small aggregates (e.g., singletons) at all costs. Typically, most everything should be aggregated by Phases 1-5. One way that we could still have unaggregated vertices is if processor p was never assigned a root node (perhaps because the number of local vertices on p is less than minNodesPerAggregate) and additionally p has local ids which are not shared with any other processors (so that no other processor's aggregate can claim these vertices).

Phase 6 looks at the first unassigned vertex and all of its local unassigned neighbors and makes a new aggregate. If this aggregate has at least minNodesPerAggregate vertices, we continue this process of creating new aggregates by examining other unassigned vertices. If the new aggregate is too small, we try add the next unassigned vertex and its neighbors to the same newly created aggregate. Once again, we check the size of this new aggregate to decide whether other unassigned vertices should be added to this aggregate or used to create a new aggregate. If the last newly created aggregate (of course there may be just one newly created aggregate) is too small, we then see if there is at least one other aggregate that this processor owns. If so, we merge the small newly created aggregate with aggregate 0. If not, we accept the fact that a small aggregate has been created.

One final note about the use of ArbitrateAndCommunicate(). No arbitration occurs (which means the procWinner[] is not set as well) for a global shared id if and only if all weights on all processors corresponding to this id is zero. Thus, the general idea is that any global id where we want arbitration to occur should have at least one associated weight on one processor which is nonzero. Any global id where we don't want any arbitration should have all weights set to 0.

Note: procWinners is also set to MyPid() by ArbitrateAndCommunicate() for any nonshared gid's with a nonzero weight.

Definition at line 71 of file MueLu_LeftoverAggregationAlgorithm_def.hpp.

template<class LocalOrdinal , class GlobalOrdinal , class Node >
void MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::RootCandidates ( my_size_t  nVertices,
ArrayView< const LO > &  vertex2AggId,
GraphBase const &  graph,
ArrayRCP< LO > &  candidates,
my_size_t nCandidates,
global_size_t nCandidatesGlobal 
) const

Build a list of candidate root nodes.

Candidates are vertices not adjacent to already aggregated vertices.

Definition at line 675 of file MueLu_LeftoverAggregationAlgorithm_def.hpp.

template<class LocalOrdinal , class GlobalOrdinal , class Node >
int MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::RemoveSmallAggs ( Aggregates aggregates,
int  min_size,
RCP< Xpetra::Vector< double, LO, GO, NO > > &  distWeights,
const MueLu::CoupledAggregationCommHelper< LO, GO, NO > &  myWidget 
) const

Attempt to clean up aggregates that are too small.

Definition at line 702 of file MueLu_LeftoverAggregationAlgorithm_def.hpp.

Member Data Documentation

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
double MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::phase3AggCreation_
private

Definition at line 311 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.

template<class LocalOrdinal = int, class GlobalOrdinal = LocalOrdinal, class Node = KokkosClassic::DefaultNode::DefaultNodeType>
int MueLu::LeftoverAggregationAlgorithm< LocalOrdinal, GlobalOrdinal, Node >::minNodesPerAggregate_
private

Definition at line 312 of file MueLu_LeftoverAggregationAlgorithm_decl.hpp.


The documentation for this class was generated from the following files: