gko::experimental::reorder::Amd#

Approximate Minimum Degree reordering. Greedy heuristic that repeatedly eliminates the vertex of lowest approximate degree from the elimination graph, producing a permutation that minimises fill-in for sparse Cholesky and LU. The standard fill-in reducer for symmetric positive-definite systems.

The numerical heavy lifting reuses the AMD routine from SuiteSparse (Tim Davis et al.); Ginkgo wraps it in the LinOpFactory interface so it returns a gko::matrix::Permutation.

template<typename IndexType = int32>
class Amd #

Inherits from

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

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

Computes an Approximate Minimum Degree (AMD) reordering of an input matrix. The implementation reuses the AMD routine from the SuiteSparse suite (Tim Davis et al.) — Ginkgo wraps it in a LinOpFactory that produces a gko::matrix::Permutation. The system matrix must therefore be a structurally-symmetric CSR matrix.

References

  • Amestoy, P. R., Davis, T. A., Duff, I. S. Algorithm 837: AMD, an Approximate Minimum Degree Ordering Algorithm. ACM Transactions on Mathematical Software, 30 (3), 381–388, 2004. https://doi.org/10.1145/1024074.1024081

Template Parameters:

IndexType – the type used to store sparsity pattern indices of the system matrix

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 AMD reordering on A + A^T, otherwise assumes that A is symmetric and uses it directly.

bool skip_sorting#

If set to false, sorts the input matrix before computing the AMD reordering. If the input matrix is not sorted by column index, the symmetrization or AMD reordering may fail silently or crash.