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#

Every Ginkgo reordering algorithm is a LinOpFactory whose generate(matrix) step returns a gko::matrix::Permutation. The 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());

For composing a reordering with a downstream solver in one shot, see ScaledReordered below.

Permutation modes#

Each matrix format’s permute(perm, mode) member 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 — 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 the row matching from MC64 plus a separate column fill-reducer from AMD), use the two-permutation overload of permute:

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`	Combine row/column scaling and a reordering as a single LinOp wrapper around an inner solver	Apply a fill-reducing reordering transparently inside a Direct or Krylov solver

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 both a permutation and a pair of diagonal scaling matrices that together push large elements onto the diagonal. It is most useful as a preprocessing step before a direct solver, where it improves pivoting stability.

Note

NestedDissection requires a METIS installation discoverable at build time (-DGINKGO_BUILD_METIS=ON).

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.
Reorder — apply AMD or nested dissection to reduce fill-in.
Factorise — pass the permuted matrix to the LU/Cholesky factorisation.
Solve — apply(b, x) runs the factorised triangular solves.

The ScaledReordered linear operator wraps steps 1–3 around any inner solver so the caller does not have to manage the permutations explicitly.

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