MatrixBandwidth.jl – Private API

const ALGORITHMS :: Dict{Symbol, Union{Dict{Symbol}, Vector}}

A dictionary indexing the data types of all available algorithms by submodule.

AbstractAlgorithm

Abstract base type for all matrix bandwidth minimization and recognition algorithms.

Interface

Concrete subtypes of AbstractAlgorithm must implement the following methods:

• Base.summary(::T) where {T<:AbstractAlgorithm}: returns a String indicating the name of the algorithm (e.g., "Gibbs–Poole–Stockmeyer").
• _requires_symmetry(::T) where {T<:AbstractAlgorithm}: returns a Bool indicating whether the algorithm requires the input matrix to be structurally symmetric.

Direct subtypes of AbstractAlgorithm must implement the following method:

• _problem(::T) where {T<:AbstractAlgorithm}: returns a Symbol indicating the matrix bandwidth problem tackled by the algorithm (e.g., :minimization).

AbstractResult

Abstract base type for all matrix bandwidth problem results.

Interface

Concrete subtypes of AbstractResult must implement parametric types

• A<:AbstractAlgorithm;
• M<:AbstractMatrix{<:Number}; and
• O<:Union{Nothing,Vector{Int}},

alongside the following fields:

• algorithm::A: the algorithm used to investigate the bandwidth.
• matrix::M: the matrix whose bandwidth is investigated.
• ordering::O: the corresponding ordering of the rows and columns, if a relevant one is found; otherwise, nothing.

NotImplementedError{Nothing}(f, subtype, abstracttype)
NotImplementedError{Symbol}(f, arg, subtype, abstracttype)

An exception indicating that a function lacks dispatch to handle a specific argument type.

Semantically, this differs from MethodError in that it connotes a developer-side failure to implement a method rather than erroneous user input. Throughout this package, it is often used to warn when an existing function with multiple dispatch on some abstract type is called on a newly created subtype for which no method has been defined.

Fields

• f::Function: the function called.
• arg::Symbol: the name of the argument with the unsupported type, if the function has multiple arguments. If the function has only one argument, this field should be set to nothing.
• subtype::Type: the type of the argument. May be the actual concrete type or some intermediate supertype. (For instance, if the relevant input has concrete type A with hierarchy A <: B <: C and the abstracttype field is C, then both A and B are perfectly valid choices for subtype.)
• abstracttype::Type: the abstract type under which the argument is meant to fall.

Constructors

• NotImplementedError(::Function, ::Type, ::Type): constructs a new NotImplementedError instance for a single-argument function. Throws an error if the second type is not abstract or the first type is not a subtype of the second.
• NotImplementedError(::Function, ::Symbol, ::Type, ::Type): constructs a new NotImplementedError instance for a multi-argument function. Throws an error if the second type is not abstract or the first type is not a subtype of the second.

Supertype Hierarchy

NotImplementedError <: Exception

RectangularMatrixError(A)

An exception indicating that the matrix A is not square.

Matrix bandwidth is only defined for square matrices, so this exception is raised when a bandwidth minimization or recognition algorithm is called with a non-square input.

Fields

• A::AbstractMatrix{<:Number}: the input matrix.
• m::Int: the number of rows of A.
• n::Int: the number of columns of A.

Constructors

• RectangularMatrixError(A::AbstractMatrix{<:Number}): constructs a new RectangularMatrixError instance, automatically inferring m and n by calling size(A).

Supertype Hierarchy

RectangularMatrixError <: Exception

StructuralAsymmetryError(A, algorithm)

An exception indicating that the matrix A is not structurally symmetric.

An n×n matrix $A$ is structurally symmetric if $A[i, j]$ is nonzero if and only if $A[j, i]$ is nonzero for $1 ≤ i, j ≤ n$. Many (albeit not all) matrix bandwidth minimization and recognition algorithms assume structural symmetry, so this exception is raised when one of these algorithms is called with a structurally asymmetric input.

Fields

• A::AbstractMatrix{<:Number}: the input matrix.
• algorithm::AbstractAlgorithm: the algorithm that was called.
• problem::Symbol: the matrix bandwidth problem tackled by the algorithm (e.g., :minimization).

Constructors

• StructuralAsymmetryError(A::AbstractMatrix{<:Number}, algorithm::AbstractAlgorithm): constructs a new StructuralAsymmetryError instance, automatically inferring problem by calling _problem(algorithm).

Supertype Hierarchy

StructuralAsymmetryError <: Exception

Notes

As noted in the error message for StructuralAsymmetryError instances, users may want to consider symmetrization techniques from [RS06] to minimize the bandwidth of structurally asymmetric matrices. (A prominent one is to simply replace $A[i, j]$ with $1$ whenever $A[i, j] = 0$ but $A[j, i] ≠ 0$.) Of course, the reliability of minimization algorithms is diminished after such a transformation, so users should proceed with caution nonetheless.

AbstractSolver <: AbstractAlgorithm

Abstract base type for all matrix bandwidth minimization solvers.

Interface

As per the interface of supertype AbstractAlgorithm, concrete subtypes of AbstractSolver must implement the following methods:

• Base.summary(::T) where {T<:AbstractSolver}: returns a String indicating the name of the solver (e.g., "Gibbs–Poole–Stockmeyer").
• _requires_symmetry(::T) where {T<:AbstractSolver}: returns a Bool indicating whether the solver requires the input matrix to be structurally symmetric.

Direct subtypes of AbstractSolver must implement the following method:

• _approach(::T) where {T<:AbstractSolver}: returns a Symbol indicating the category of solver (e.g., :heuristic).

Supertype Hierarchy

AbstractSolver <: AbstractAlgorithm

ExactSolver <: AbstractSolver <: AbstractAlgorithm

Abstract type for all exact matrix bandwidth minimization solvers.

Exact methods are those which guarantee an optimal ordering producing the true minimum bandwidth of a matrix. Since bandwidth minimization is an NP-complete problem, existing exact algorithms are, at best, exponential in time complexity—much worse than many polynomial-time heuristic approaches (e.g., Gibbs–Poole–Stockmeyer). Such methods, therefore, are not feasible for large matrices, but they remain useful when precise solutions are required for small-to-medium-sized inputs (say, up to $100×100$).

Supertype Hierarchy

ExactSolver <: AbstractSolver <: MatrixBandwidth.AbstractAlgorithm

HeuristicSolver <: AbstractSolver <: AbstractAlgorithm

Abstract type for all heuristic matrix bandwidth minimization solvers.

Heuristic methods are those which aim to produce near-optimal solutions in a more performant manner than exact methods. While precise bandwidth minimization is NP-complete, many heuristic algorithms (such as Gibbs–Poole–Stockmeyer) run in polynomial time.

Heuristic algorithms differ from metaheuristic ones in that they do not employ higher-level iterative search frameworks (e.g., stochastic techniques) to survey the global search space and escape local minima; instead, they rely on straightforward deterministic procedures to find good solutions in a single pass.

Supertype Hierarchy

HeuristicSolver <: AbstractSolver <: MatrixBandwidth.AbstractAlgorithm

pseudo_peripheral_node(A::AbstractMatrix{Bool}) -> Int

Select a pseudo-peripheral node from the connected graph represented by A.

This function acts as a node selector for heuristic matrix bandwidth minimization algorithms such as reverse Cuthill–McKee and Gibbs–Poole–Stockmeyer when applies to connected graphs (or their adjacency matrices). It heuristically identifies the node "farthest" from the others in the graph as a good starting point for the search process.

It is assumed that A is the adjacency matrix of some connected, undirected graph; otherwise, undefined behavior may arise.

Arguments

• A::AbstractMatrix{Bool}: a symmetric matrix with boolean entries, acting as the adjacency matrix of some connected undirected graph.

Returns

• Int: the index of the pseudo-peripheral node selected from the graph.

Notes

This function takes heavy inspiration from the implementation in [Net25], which accepts a graph object as input and leverages several pre-existing functions in the networkx library. We herein repurpose the logic to work directly on adjacency matrices, avoiding reallocation overhead and an unnecessary dependency on Graphs.jl.

[TODO: Specify the actual academic source for this, not just the NetworkX one.]

MetaheuristicSolver <: AbstractSolver <: AbstractAlgorithm

Abstract type for all metaheuristic matrix bandwidth minimization solvers.

Metaheuristic methods are those which employ higher-level iterative search frameworks such as stochastic techniques or nature-inspired processes to survey the global search space and escape local minima. Unlike heuristic methods—which follow fixed deterministic procedures—metaheuristics adaptively refine candidate solutions over multiple iterations. Although metaheuristic approaches are often slower than heuristic ones (but certainly still faster than exact ones), they shine in complex cases where the latter may get trapped in poor-quality local minima.

Supertype Hierarchy

MetaheuristicSolver <: AbstractSolver <: MatrixBandwidth.AbstractAlgorithm

AbstractDecider <: AbstractAlgorithm

Abstract base type for all matrix bandwidth recognition deciders.

Interface

As per the interface of supertype AbstractAlgorithm, concrete subtypes of AbstractDecider must implement the following methods:

• Base.summary(::T) where {T<:AbstractDecider}: returns a String indicating the name of the decider (e.g., "Caprara–Salazar-González").
• _requires_symmetry(::T) where {T<:AbstractDecider}: returns a Bool indicating whether the decider requires the input matrix to be structurally symmetric.

Supertype Hierarchy

AbstractDecider <: AbstractAlgorithm

dcm_ps_optimal_depth(A::AbstractMatrix{Bool}) -> Int

Compute a (hopefully) near-optimal Del Corso–Manzini perimeter search depth for A.

Taking experimental results from [DM99, pp. 197–199] into account, this function tries to approximate the optimal depth parameter as a function of both matrix size and density. This depth parameter determines how large of a "perimeter" of last-placed indices is precomputed in the Del Corso–Manzini algorithm with perimeter search.

Arguments

• A::AbstractMatrix{Bool}: the (structurally symmetric and square) input matrix whose bandwidth is investigated.

Returns

• ::Int: a (hopefully) near-optimal perimeter search depth for the Del Corso–Manzini algorithm with perimeter search on A.

Notes

See Tables 4, 5, and 6 from the original paper for more details on experimental results regarding the optimal perimeter search depth [DM99, pp. 197–199].

See also DelCorsoManziniWithPS and MatrixBandwidth.Minimization.Exact.DelCorsoManziniWithPS) for our implementation of the relevant bandwidth recognition and bandwidth minimization algorithms, respectively.