gko::experimental::reorder::Mc64#

MC64 row permutation. Maximises the product (or sum) of absolute diagonal entries by solving a bipartite matching problem, optionally returning row and column scalings that bring all diagonal entries to unit magnitude. The classical pre-step for sparse LU factorisations of indefinite / non-symmetric systems.

The returned object is a ScaledPermutation, so applying it both permutes and scales the matrix in a single pass.

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

Inherits from

  • public gko::EnablePolymorphicObject<Mc64<default_precision, int32>, LinOpFactory>

  • public gko::EnablePolymorphicAssignment<Mc64<default_precision, int32>>

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 \(c(i, j) = a_i - |a(i, j)|\) 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

Public Functions

inline const parameters_type &get_parameters() const#

Returns the parameters used to construct the factory.

Returns:

the parameters used to construct the factory.

std::unique_ptr<result_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 ScaledPermutation 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

mc64_strategy strategy#

This parameter controls the goal of the permutation.

remove_complex<ValueType> tolerance#

This parameter controls the tolerance below which a weight is considered to be zero.