gko::reorder::Rcm< ValueType, IndexType > Class Template Reference

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

Inheritance diagram for gko::reorder::Rcm< ValueType, IndexType >:

Classes
class	Factory
struct	parameters_type

Public Types
using	SparsityMatrix = matrix::SparsityCsr< ValueType, IndexType >
using	PermutationMatrix = matrix::Permutation< IndexType >
using	value_type = ValueType
using	index_type = IndexType
Public Types inherited from gko::EnablePolymorphicAssignment< ConcreteType, ResultType >
using	result_type = ResultType
Public Types inherited from gko::ConvertibleTo< ResultType >
using	result_type = ResultType

Public Member Functions
std::shared_ptr< const PermutationMatrix >	get_permutation () const
std::shared_ptr< const PermutationMatrix >	get_inverse_permutation () const
const parameters_type &	get_parameters () const
Public Member Functions inherited from gko::EnableAbstractPolymorphicObject< AbstractObject, PolymorphicBase >
std::unique_ptr< AbstractObject >	create_default (std::shared_ptr< const Executor > exec) const
std::unique_ptr< AbstractObject >	create_default () const
std::unique_ptr< AbstractObject >	clone (std::shared_ptr< const Executor > exec) const
std::unique_ptr< AbstractObject >	clone () const
AbstractObject *	copy_from (const PolymorphicObject *other)
template<typename Derived >
std::enable_if_t< std::is_base_of< PolymorphicObject, std::decay_t< Derived > >::value, AbstractObject > *	copy_from (std::unique_ptr< Derived > &&other)
template<typename Derived >
std::enable_if_t< std::is_base_of< PolymorphicObject, std::decay_t< Derived > >::value, AbstractObject > *	copy_from (const std::unique_ptr< Derived > &other)
AbstractObject *	copy_from (const std::shared_ptr< const PolymorphicObject > &other)
AbstractObject *	move_from (ptr_param< PolymorphicObject > other)
AbstractObject *	clear ()
Public Member Functions inherited from gko::PolymorphicObject
PolymorphicObject &	operator= (const PolymorphicObject &)
std::unique_ptr< PolymorphicObject >	create_default (std::shared_ptr< const Executor > exec) const
std::unique_ptr< PolymorphicObject >	create_default () const
std::unique_ptr< PolymorphicObject >	clone (std::shared_ptr< const Executor > exec) const
std::unique_ptr< PolymorphicObject >	clone () const
PolymorphicObject *	copy_from (const PolymorphicObject *other)
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)
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)
PolymorphicObject *	copy_from (const std::shared_ptr< const PolymorphicObject > &other)
PolymorphicObject *	move_from (ptr_param< PolymorphicObject > other)
PolymorphicObject *	clear ()
std::shared_ptr< const Executor >	get_executor () const noexcept
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< ConcreteType, ResultType >
void	convert_to (result_type *result) const override
void	move_to (result_type *result) override
Public Member Functions inherited from gko::ConvertibleTo< ResultType >
void	convert_to (ptr_param< result_type > result) const
void	move_to (ptr_param< result_type > result)

Static Public Member Functions
static auto	build () -> decltype(Factory ::create())

Protected Member Functions
	Rcm (std::shared_ptr< const Executor > exec)
	Rcm (const Factory *factory, const ReorderingBaseArgs &args)
Protected Member Functions inherited from gko::EnablePolymorphicObject< ConcreteObject, PolymorphicBase >
std::unique_ptr< PolymorphicObject >	create_default_impl (std::shared_ptr< const Executor > exec) const override
PolymorphicObject *	copy_from_impl (const PolymorphicObject *other) override
PolymorphicObject *	copy_from_impl (std::unique_ptr< PolymorphicObject > other) override
PolymorphicObject *	move_from_impl (PolymorphicObject *other) override
PolymorphicObject *	move_from_impl (std::unique_ptr< PolymorphicObject > other) override
PolymorphicObject *	clear_impl () override
Protected Member Functions inherited from gko::PolymorphicObject
	PolymorphicObject (std::shared_ptr< const Executor > exec)
	PolymorphicObject (const PolymorphicObject &other)
Protected Member Functions inherited from gko::log::EnableLogging< PolymorphicObject >
void	log (Params &&... params) const

Friends
class	EnablePolymorphicObject< Rcm, ReorderingBase< IndexType > >

Additional Inherited Members
Protected Attributes inherited from gko::log::EnableLogging< PolymorphicObject >
std::vector< std::shared_ptr< const Logger > >	loggers_

Detailed Description

template<typename ValueType = default_precision, typename IndexType = int32>
class gko::reorder::Rcm< ValueType, 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. It requires the input matrix to be structurally symmetric.

Note

This class is derived from polymorphic object but is not a LinOp as it does not make sense for this class to implement the apply methods. The objective of this class is to generate a reordering/permutation vector (in the form of the Permutation matrix), which can be used to apply to reorder a matrix as required.

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

ValueType	Type of the values of all matrices used in this class
IndexType	Type of the indices of all matrices used in this class

Member Function Documentation

get_inverse_permutation()

template<typename ValueType = default_precision, typename IndexType = int32>

std::shared_ptr< const PermutationMatrix > gko::reorder::Rcm< ValueType, IndexType >::get_inverse_permutation ( ) const

inline

Gets the inverse permutation (permutation matrix, output of the algorithm) of the linear operator.

Returns

the inverse permutation (permutation matrix)

get_permutation()

template<typename ValueType = default_precision, typename IndexType = int32>

std::shared_ptr< const PermutationMatrix > gko::reorder::Rcm< ValueType, IndexType >::get_permutation ( ) const

inline

Gets the permutation (permutation matrix, output of the algorithm) of the linear operator.

Returns

the permutation (permutation matrix)

---

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

• ginkgo/core/reorder/rcm.hpp