gko::experimental::reorder::Rcm#

Reverse Cuthill–McKee bandwidth reduction. Builds a permutation that clusters non-zeros near the diagonal — useful as a fill-in pre-conditioner for sparse Cholesky / LU and as a cache-locality hint for triangular solves.

template<typename IndexType = int32>
class Rcm #

Inherits from

  • public gko::EnablePolymorphicObject<Rcm<int32>, LinOpFactory>

  • public gko::EnablePolymorphicAssignment<Rcm<int32>>

Rcm (Reverse Cuthill-McKee) is a reordering algorithm minimizing the bandwidth of a matrix. Such a reordering typically also significantly reduces fill-in, though usually not as effective as more complex algorithms, specifically AMD and nested dissection schemes. The advantage of this algorithm is its low runtime.

The class is a LinOpFactory generating a Permutation matrix out of a Csr system matrix, to be used with Csr::permute(...).

There are two “starting strategies” currently available: minimum degree and pseudo-peripheral. These strategies control how a starting vertex for a connected component is chosen, which is then renumbered as first vertex in the component, starting the algorithm from there. In general, the bandwidths obtained by choosing a pseudo-peripheral vertex are slightly smaller than those obtained from choosing a vertex of minimum degree. On the other hand, this strategy is much more expensive, relatively. The algorithm for finding a pseudo-peripheral vertex as described in “Computer Solution of Sparse Linear Systems” (George, Liu, Ng, Oak Ridge National Laboratory, 1994) is implemented here.

Template Parameters:

IndexType – Type of the indices of all matrices used in this class

Public Functions

inline const parameters_type &get_parameters()#

Returns the parameters used to construct the factory.

Returns:

the parameters used to construct the factory.

std::unique_ptr<permutation_type> generate(
std::shared_ptr<const LinOp> system_matrix,
) const#

Creates a new product from the given components.

The method will create an ComponentsType object from the arguments of this method, and pass it to the generate_impl() function which will create a new AbstractProductType.

Note

This function overrides the default LinOpFactory::generate to return a Permutation instead of a generic LinOp, which would need to be cast to Permutation again to access its indices. It is only necessary because smart pointers aren’t covariant.

Template Parameters:

Args – types of arguments passed to the constructor of ComponentsType

Parameters:

args – arguments passed to the constructor of ComponentsType

Returns:

an instance of AbstractProductType

Public Static Functions

static inline parameters_type build()#

Creates a new parameter_type to set up the factory.

struct parameters_type #

Inherits from

Public Members

bool skip_symmetrize#

If set to false, computes the RCM reordering on A + A^T, otherwise assumes that A is symmetric and uses it directly.

rcm_starting_strategy strategy#

This parameter controls the strategy used to determine a starting vertex.