MC64 is an algorithm for permuting large entries to the diagonal of a sparse matrix. More...

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

Inheritance diagram for gko::experimental::reorder::Mc64< ValueType, IndexType >:

Collaboration diagram for gko::experimental::reorder::Mc64< ValueType, IndexType >:

Classes
struct	parameters_type

Public Types
using	value_type = ValueType

using	index_type = IndexType

using	result_type = Composition< value_type >

using	matrix_type = matrix::Csr< value_type, index_type >

Public Types inherited from gko::EnablePolymorphicAssignment< Mc64< ValueType, IndexType > >
using	result_type = Mc64< ValueType, IndexType >

Public Types inherited from gko::ConvertibleTo< Mc64< ValueType, IndexType > >
using	result_type = Mc64< ValueType, IndexType >

Public Member Functions
const parameters_type &	get_parameters () const
	Returns the parameters used to construct the factory. More...

std::unique_ptr< result_type >	generate (std::shared_ptr< const LinOp > system_matrix) const

Public Member Functions inherited from gko::EnableAbstractPolymorphicObject< Mc64< ValueType, IndexType >, LinOpFactory >
std::unique_ptr< Mc64< ValueType, IndexType > >	create_default (std::shared_ptr< const Executor > exec) const

std::unique_ptr< Mc64< ValueType, IndexType > >	create_default () const

std::unique_ptr< Mc64< ValueType, IndexType > >	clone (std::shared_ptr< const Executor > exec) const

std::unique_ptr< Mc64< ValueType, IndexType > >	clone () const

Mc64< ValueType, IndexType > *	copy_from (const PolymorphicObject *other)

std::enable_if_t< std::is_base_of< PolymorphicObject, std::decay_t< Derived > >::value, Mc64< ValueType, IndexType > > *	copy_from (std::unique_ptr< Derived > &&other)

std::enable_if_t< std::is_base_of< PolymorphicObject, std::decay_t< Derived > >::value, Mc64< ValueType, IndexType > > *	copy_from (const std::unique_ptr< Derived > &other)

Mc64< ValueType, IndexType > *	copy_from (const std::shared_ptr< const PolymorphicObject > &other)

Mc64< ValueType, IndexType > *	move_from (ptr_param< PolymorphicObject > other)

Mc64< ValueType, 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< Mc64< ValueType, 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< Mc64< ValueType, 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< Mc64< ValueType, IndexType >, LinOpFactory >

class	enable_parameters_type< parameters_type, Mc64< ValueType, IndexType > >

Detailed Description

template<typename ValueType = default_precision, typename IndexType = int32>
class gko::experimental::reorder::Mc64< ValueType, IndexType >

MC64 is an algorithm for permuting large entries to the diagonal of a sparse matrix.

This approach can increase numerical stability of e.g. an LU factorization without pivoting. Under the assumption of working on a nonsingular square matrix, the algorithm computes a minimum weight perfect matching on a weighted edge bipartite graph of the matrix. It is described in detail in "On Algorithms for Permuting Large Entries to the Diagonal of a Sparse Matrix" (Duff, Koster, 2001, DOI: 10.1137/S0895479899358443). There are two strategies for choosing the weights supported:

Maximizing the product of the absolute values on the diagonal. For this strategy, the weights are computed as $c(i, j) = \log_2(a_i) - \log_2(|a(i, j)|)$ if $a(i, j) \neq 0$ and $c(i, j) = \infty$ otherwise. Here, a_i is the maximum absolute value in row i of the matrix A. In this case, the implementation computes a row permutation P and row and column scaling coefficients L and R such that the matrix P*L*A*R has values with unity absolute value on the diagonal and smaller or equal entries everywhere else.
Maximizing the sum of the absolute values on the diagonal. For this strategy, the weights are computed as if $a(i, j) \neq 0$ and $c(i, j) = \infty$ otherwise. In this case, no scaling coefficients are computed.

This class creates a Combination of two ScaledPermutations representing the row and column permutation and scaling factors computed by this algorithm.

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

◆ generate()

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

std::unique_ptr<result_type> gko::experimental::reorder::Mc64< ValueType, 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 ScaledPermutation again to access its indices. It is only necessary because smart pointers aren't covariant.

◆ get_parameters()

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

const parameters_type& gko::experimental::reorder::Mc64< ValueType, IndexType >::get_parameters ( ) const

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/mc64.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

template<typename ValueType = default_precision, typename IndexType = int32> class gko::experimental::reorder::Mc64< ValueType, IndexType >

Member Function Documentation

◆ generate()

◆ get_parameters()

template<typename ValueType = default_precision, typename IndexType = int32>
class gko::experimental::reorder::Mc64< ValueType, IndexType >