`gko::multigrid::Pgm`#

Parallel Graph Matching aggregation: Ginkgo’s default algebraic coarsening. Pgm builds the coarse level by aggregating fine-level rows in two steps:

For every unaggregated row \(i\), find the strongest neighbour: the column \(j\) with the largest symmetric weight \((|a_{ij}| + |a_{ji}|)/2\), divided by the larger of the diagonal entries \(|a_{ii}|\) and \(|a_{jj}|\).
Match rows whose strongest-neighbour relation is mutual (row \(i\) picks \(j\) and row \(j\) picks \(i\)), forming aggregates of size 2.

Steps 1 and 2 are repeated until max_iterations passes (default 15) have run, a pass makes no new match, or the number of unaggregated rows drops below max_unassigned_ratio (default 0.05) times the number of rows; the remaining rows are then attached to a neighbouring aggregate or left as singletons. The current implementation forms aggregates of size 2 (one-phase handshaking); the coarse operator is built by Galerkin projection \(A_c = R\, A\, P\).

The Pgm factory supports generate_reuse(): once a matrix has been recorded, later matrices with the same sparsity pattern keep its aggregates and only the coarse matrix is recomputed. The aggregates come from the values of the first matrix, so it should be representative of the later ones.

Attention

The reuse interface is experimental and may change.

Pgm is the natural default coarsening for non-geometric problems where no separator information is available; graph matching captures the strongest couplings using the matrix values themselves. Pgm accepts gko::experimental::distributed::Matrix as well as Csr matrices.

template<typename ValueType = default_precision, typename IndexType = int32> class Pgm #

Inherits from

public gko::LinOp
public gko::multigrid::EnableMultigridLevel<default_precision>

Parallel graph match (Pgm

) is the aggregate method introduced in the paper M. Naumov et al., “AmgX: A Library for GPU Accelerated Algebraic

Multigrid and Preconditioned Iterative Methods”. Current implementation only contains size = 2 version.

Pgm creates the aggregate group according to the matrix value not the structure. Pgm gives two steps (one-phase handshaking) to group the elements. 1: get the strongest neighbor of each unaggregated element. 2: group the elements whose strongest neighbor is each other. repeating until reaching the given conditions. After that, the un-aggregated elements are assigned to an aggregated group or are left alone.

The factory supports LinOpFactory::generate_reuse(): later calls on a matrix with the same sparsity pattern keep the aggregates and only recompute the coarse matrix, so the result can differ from generate(). The aggregates come from the values of the first matrix, so it should be representative of the later ones.

Template Parameters:

ValueType – precision of matrix elements
IndexType – precision of matrix indexes

Public Functions

inline std::shared_ptr<const LinOp> get_system_matrix() const#

Returns the system operator (matrix) of the linear system.

Returns:: the system operator (matrix)

inline IndexType *get_agg() noexcept#

Returns the aggregate group.

Aggregate group whose size is same as the number of rows. Stores the mapping information from row index to coarse row index. i.e., agg[row_idx] = coarse_row_idx.

Returns:: the aggregate group.

inline const IndexType *get_const_agg() const noexcept#

Returns the aggregate group.

Aggregate group whose size is same as the number of rows. Stores the mapping information from row index to coarse row index. i.e., agg[row_idx] = coarse_row_idx.

Note

This is the constant version of the function, which can be significantly more memory efficient than the non-constant version, so always prefer this version.

Returns:: the aggregate group.

Public Static Functions

static parameters_type parse( const config::pnode &config, const config::registry &context, const config::type_descriptor &td_for_child = config::make_type_descriptor<ValueType, IndexType>(), )#

Create the parameters from the property_tree. Because this is directly tied to the specific type, the value/index type settings within config are ignored and type_descriptor is only used for children configs.

Parameters:

config – the property tree for setting
context – the registry
td_for_child – the type descriptor for children configs. The default uses the value/index type of this class.

Returns:

parameters

struct parameters_type#

Public Members

unsigned max_iterations#: The maximum number of iterations. We use the same default value as NVIDIA AMGX Reference Manual (October 2017, API Version 2, NVIDIA/AMGX).

double max_unassigned_ratio#: The maximum ratio of unassigned number, which is valid in the interval 0.0 ~ 1.0. We use the same default value as NVIDIA AMGX Reference Manual (October 2017, API Version 2, NVIDIA/AMGX).

bool deterministic#

Use the deterministic assign_to_exist_agg method or not.

If deterministic is set to true, always get the same aggregated group from the same matrix. Otherwise, the aggregated group might be different depending on the execution ordering.

bool skip_sorting#: The system_matrix, which will be given to this factory, must be sorted (first by row, then by column) in order for the algorithm to work. If it is known that the matrix will be sorted, this parameter can be set to true to skip the sorting (therefore, shortening the runtime). However, if it is unknown or if the matrix is known to be not sorted, it must remain false, otherwise, this multigrid_level might be incorrect.

class reuse_data_type #

Inherits from

public gko::LinOpFactory::ReuseData

Records the aggregates, the transfer operators and the coarse-to-fine mappings of the first generate_reuse() call.

gko::multigrid::Pgm#

`gko::multigrid::Pgm`#