Reordering and permutations#

A reordering computes a permutation of the rows and columns of a sparse matrix that makes downstream operations cheaper or more numerically robust. The most common motivation is reducing fill-in during sparse direct factorisation (LU, Cholesky), but reorderings also reduce bandwidth for triangular solves, expose diagonal dominance for preconditioning, and balance work across processes. This page surveys Ginkgo’s reordering algorithms, explains the common interface, and points to per-algorithm pages for detail.

What a reordering produces#

Amd, Rcm and NestedDissection are LinOpFactory classes whose generate(matrix) step returns a gko::matrix::Permutation. Mc64 returns a gko::Composition of two gko::matrix::ScaledPermutation operators (see MC64). A permutation can then be applied to the matrix (permuted = P * A * P^T) and to the right-hand side / solution as needed:

auto reorder_factory = gko::experimental::reorder::Amd<int>::build().on(exec);
auto perm = reorder_factory->generate(system_matrix);

// Apply: row+column permutation for a symmetric system
auto permuted = system_matrix->permute(perm.get());

To wrap fixed diagonal scalings and an RCM reordering around an inner solver, see ScaledReordered.

Permutation modes#

Csr and Dense provide a permute(perm, mode) member that takes a permute_mode enum that controls how the permutation is applied. The enum is a 3-bit mask combining rows, columns, and inverse:

Mode	Effect on `A`	Typical use
`permute_mode::none`	\(A' = A\)	No-op (mask cleared).
`permute_mode::rows`	\(A' = P A\)	Permute rows only.
`permute_mode::columns`	\(A' = A P^T\)	Permute columns only.
`permute_mode::symmetric` (default)	\(A' = P A P^T\)	Symmetric reordering, the standard pre-factorisation transform.
`permute_mode::inverse_rows`	\(A' = P^{-1} A\)	Undo a previous row permutation.
`permute_mode::inverse_columns`	\(A' = A P^{-T}\)	Undo a previous column permutation.
`permute_mode::inverse_symmetric`	\(A' = P^{-1} A P^{-T}\)	Undo a symmetric reordering (e.g., to map a solution computed in the permuted system back to the original variable order).

The fundamental modes can be combined with the bitwise |, &, and ^ operators: rows | inverse is the same as inverse_rows, and so on.

gko::matrix::Permutation<IndexType> exposes two more helpers for working with permutations directly:

auto inv  = perm->compute_inverse();         // P^{-1}
auto comp = perm1->compose(perm2);           // P_2 * P_1 — apply perm1 first, then perm2

compute_inverse() returns P^{-1} as a new Permutation object. compose(other) combines two permutations so that applying the result is equivalent to applying this first and then other, which is useful when you want to chain a fill-reducing reordering with a separate parallel-partitioning reordering, for instance.

For non-symmetric problems where rows and columns should be permuted by different permutations (for example a row permutation and a column permutation generated by two separate reorderings, each a Permutation), use the two-permutation overload of permute. MC64’s scaled permutations go through Csr::scale_permute instead:

auto permuted = matrix->permute(row_perm.get(), col_perm.get());

The available algorithms#

Algorithm	Class	Goal	Typical use
RCM	`gko::experimental::reorder::Rcm`	Bandwidth / profile reduction	Preconditioning, banded triangular solves
AMD	`gko::experimental::reorder::Amd`	Minimise fill-in (approximate minimum degree)	Sparse direct factorisation
MC64	`gko::experimental::reorder::Mc64`	Maximise diagonal product (matching)	Numerical stability for direct solvers
Nested dissection	`gko::experimental::reorder::NestedDissection`	Recursive bisection-based ordering	Large finite-element / FD systems on parallel hardware
ScaledReordered	`gko::experimental::reorder::ScaledReordered`	Wrap user-supplied diagonal row/column scalings and an RCM reordering around an inner solver	Solve the scaled, reordered system while the caller keeps the original variable order

All five live in gko::experimental::reorder. The non-experimental gko::reorder::Rcm still exists but is deprecated in favour of the experimental version, which integrates more cleanly with the rest of the reordering API.

Note

Mc64 is technically a scaling and matching, not just a permutation: it produces a row permutation with row scaling and a column scaling, returned as a Composition of two ScaledPermutation operators, that together push large elements onto the diagonal. It is most useful as a preprocessing step before Ginkgo’s Lu, which factorises without pivoting: MC64 can increase the numerical stability of that factorisation.

Note

NestedDissection is available when CMake finds METIS at configure time. Set -DMETIS_DIR=<prefix> (or add the prefix to CMAKE_PREFIX_PATH) to point CMake at a non-standard METIS installation.

Why reorder before a direct solver#

Sparse LU and Cholesky factorisations introduce fill-in: zeros in the original matrix that become non-zero in L or U. The amount of fill-in depends strongly on the row/column ordering. A naïve ordering can produce a factorisation many orders of magnitude larger than the original matrix; a fill-reducing reordering (AMD, nested dissection) typically keeps the factorisation tractable.

The recommended pre-processing recipe for a sparse direct solver is:

Match (optional): apply MC64 to push large entries onto the diagonal (Csr::scale_permute applies its row and column scaled permutations).
Reorder: apply AMD or nested dissection to reduce fill-in (Csr::permute).
Factorise: pass the permuted matrix to the LU/Cholesky factorisation.
Solve: permute b (and apply the MC64 row scaling) the same way, call apply(b, x) for the factorised triangular solves, then map x back with the inverse permutation (and column scaling); Tune a direct solver shows the full sequence.

Without ScaledReordered, apply the transforms yourself with Csr::permute and Csr::scale_permute before handing the matrix to the factorisation. ScaledReordered covers the case of fixed diagonal scalings plus an RCM reordering around any inner solver.

When to reorder for iterative solvers#

Reordering helps Krylov methods less directly, but is still useful in two scenarios:

As a preprocessing step for an ILU/IC preconditioner: incomplete factorisations also benefit from fill-reducing reorderings; an RCM or AMD pass before computing the preconditioner can substantially change its quality.
For cache locality on long triangular solves: RCM compacts the bandwidth of the matrix, which can speed up the LowerTrs / UpperTrs kernels used inside ILU and direct solves on CPU.

Per-algorithm pages#

Reordering algorithms