MatrixBandwidth.jl: Fast algorithms for matrix bandwidth minimization and recognition

Read full text
Authors: Varona, Luis M. B.
Cited by: 0

Abstract

v0.3.0 implements several major performance improvements to the Caprara–Salazar–González, Del Corso–Manzini, and Gibbs–Poole–Stockmeyer algorithms. (The original implementations had a few minor discrepancies with the original paper affecting performance, but not correctness.) Furthermore, it changes the default recognition decider from DelCorsoManzini to CapraraSalazarGonzalez (which is now faster)—arguably a breaking change, contributing to the decision to bump to a new minor version. Changed Switched back from @repl blocks to jldoctest blocks in the docstrings, since Documenter.jl stopped executing @repl blocks in the generated documentation (#217). Switched from recomputing Del Corso–Manzini placement deadlines from scratch each step to maintaining them incrementally as nodes are placed, incorporating the last missing optimization from the paper (#216). Changed the default recognition decider from Del Corso–Manzini to Caprara–Salazar-González, which is now considerably faster after the performance fixes (#214). Updated the _blb_connected helper (used in bandwidth_lower_bound) to avoid unnecessary allocations, now requiring only O(n) auxiliary space instead of O(n^2) (#213). Fixed Fixed minor discrepancy (not affecting correctness, only performance) between the Saxe–Gurari–Sudborough implementation and the original paper; now, candidates are pruned early when a node in the active region is already at its maximum number of allowed dangling edges (and so the next node must be adjacent to it) (#215). Significantly refactored the Caprara–Salazar-González logic to fix several bugs severely affecting performance (although not correctness); this also allowed us to remove JuMP.jl and HiGHS.jl as dependencies (#214). Fixed off-by-one bug in the expiration-time pruning of the Del Corso–Manzini algorithm(s) (did not affect correctness, only performance) (#211). Fixed several discrepancies between the Gibbs–Poole–Stockmeyer minimization algorithm as described in the original paper and its implementation (the README and tutorial examples was also updated accordingly) (#209). Removed Removed nightly CI runs (on pre) from the GitHub Actions CI workflow, since they often fail due to incompatibilities with dependencies in the testing matrix (#212).

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
29 January 2026
Language
EN