gko::experimental::reorder::Rcm< IndexType > Class Template Reference

Rcm (Reverse Cuthill-McKee) is a reordering algorithm minimizing the bandwidth of a matrix. More...

#include <ginkgo/core/reorder/rcm.hpp>

Inheritance diagram for gko::experimental::reorder::Rcm< IndexType >:

Collaboration diagram for gko::experimental::reorder::Rcm< IndexType >:

Classes
struct	parameters_type

Public Types
using	index_type = IndexType
using	permutation_type = matrix::Permutation< index_type >
Public Types inherited from gko::EnablePolymorphicAssignment< Rcm< IndexType > >
using	result_type = Rcm< IndexType >
Public Types inherited from gko::ConvertibleTo< Rcm< IndexType > >
using	result_type = Rcm< IndexType >

Public Member Functions
const parameters_type &	get_parameters ()
	Returns the parameters used to construct the factory. More...
std::unique_ptr< permutation_type >	generate (std::shared_ptr< const LinOp > system_matrix) const
Public Member Functions inherited from gko::EnableAbstractPolymorphicObject< Rcm< IndexType >, LinOpFactory >
std::unique_ptr< Rcm< IndexType > >	create_default (std::shared_ptr< const Executor > exec) const
std::unique_ptr< Rcm< IndexType > >	create_default () const
std::unique_ptr< Rcm< IndexType > >	clone (std::shared_ptr< const Executor > exec) const
std::unique_ptr< Rcm< IndexType > >	clone () const
Rcm< IndexType > *	copy_from (const PolymorphicObject *other)
std::enable_if_t< std::is_base_of< PolymorphicObject, std::decay_t< Derived > >::value, Rcm< IndexType > > *	copy_from (std::unique_ptr< Derived > &&other)
std::enable_if_t< std::is_base_of< PolymorphicObject, std::decay_t< Derived > >::value, Rcm< IndexType > > *	copy_from (const std::unique_ptr< Derived > &other)
Rcm< IndexType > *	copy_from (const std::shared_ptr< const PolymorphicObject > &other)
Rcm< IndexType > *	move_from (ptr_param< PolymorphicObject > other)
Rcm< IndexType > *	clear ()
Public Member Functions inherited from gko::LinOpFactory
std::unique_ptr< LinOp >	generate (std::shared_ptr< const LinOp > input) const
Public Member Functions inherited from gko::PolymorphicObject
PolymorphicObject &	operator= (const PolymorphicObject &)
std::unique_ptr< PolymorphicObject >	create_default (std::shared_ptr< const Executor > exec) const
	Creates a new "default" object of the same dynamic type as this object. More...
std::unique_ptr< PolymorphicObject >	create_default () const
	Creates a new "default" object of the same dynamic type as this object. More...
std::unique_ptr< PolymorphicObject >	clone (std::shared_ptr< const Executor > exec) const
	Creates a clone of the object. More...
std::unique_ptr< PolymorphicObject >	clone () const
	Creates a clone of the object. More...
PolymorphicObject *	copy_from (const PolymorphicObject *other)
	Copies another object into this object. More...
template<typename Derived , typename Deleter >
std::enable_if_t< std::is_base_of< PolymorphicObject, std::decay_t< Derived > >::value, PolymorphicObject > *	copy_from (std::unique_ptr< Derived, Deleter > &&other)
	Moves another object into this object. More...
template<typename Derived , typename Deleter >
std::enable_if_t< std::is_base_of< PolymorphicObject, std::decay_t< Derived > >::value, PolymorphicObject > *	copy_from (const std::unique_ptr< Derived, Deleter > &other)
	Copies another object into this object. More...
PolymorphicObject *	copy_from (const std::shared_ptr< const PolymorphicObject > &other)
	Copies another object into this object. More...
PolymorphicObject *	move_from (ptr_param< PolymorphicObject > other)
	Moves another object into this object. More...
PolymorphicObject *	clear ()
	Transforms the object into its default state. More...
std::shared_ptr< const Executor >	get_executor () const noexcept
	Returns the Executor of the object. More...
Public Member Functions inherited from gko::log::EnableLogging< PolymorphicObject >
void	add_logger (std::shared_ptr< const Logger > logger) override
void	remove_logger (const Logger *logger) override
void	remove_logger (ptr_param< const Logger > logger)
const std::vector< std::shared_ptr< const Logger > > &	get_loggers () const override
void	clear_loggers () override
Public Member Functions inherited from gko::log::Loggable
void	remove_logger (ptr_param< const Logger > logger)
Public Member Functions inherited from gko::EnablePolymorphicAssignment< Rcm< IndexType > >
void	convert_to (result_type *result) const override
	Converts the implementer to an object of type result_type. More...
void	move_to (result_type *result) override
	Converts the implementer to an object of type result_type by moving data from this object. More...
Public Member Functions inherited from gko::ConvertibleTo< Rcm< IndexType > >
void	convert_to (ptr_param< result_type > result) const
void	move_to (ptr_param< result_type > result)

Static Public Member Functions
static parameters_type	build ()
	Creates a new parameter_type to set up the factory.

Friends
class	EnablePolymorphicObject< Rcm< IndexType >, LinOpFactory >
class	enable_parameters_type< parameters_type, Rcm< IndexType > >

Detailed Description

template<typename IndexType = int32>
class gko::experimental::reorder::Rcm< IndexType >

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

Member Function Documentation

generate()

template<typename IndexType = int32>

std::unique_ptr<permutation_type> gko::experimental::reorder::Rcm< IndexType >::generate

(

std::shared_ptr< const LinOp >

system_matrix

)

const

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.

get_parameters()

template<typename IndexType = int32>

const parameters_type& gko::experimental::reorder::Rcm< IndexType >::get_parameters ( )

inline

Returns the parameters used to construct the factory.

Returns

the parameters used to construct the factory.

---

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

• ginkgo/core/reorder/rcm.hpp