v0.3.0

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).

v0.2.3

Changed

• Made a few micro-optimizations to the Saxe–Gurari–Sudborough recognition decider (e.g., avoiding unnecessary duplicate checks/moving computations to later in the control flow when appropriate) (#204, #205).
• Replaced processed and visited sets in the Saxe–Gurari–Sudborough recognition decider with boolean arrays to improve performance (#203).
• Updated CONTRIBUTING.md with a paragraph about adding to the changelog, as well as a minor typo fix (#202).
• Raised the threshold for number of JET reports in static analysis testing from 20 to 30 (#201).
• Updated the metadata in the documentation (including changing CITATION.bib to CITATION.cff) to reflect JOSS publication (#198).

v0.2.2

Added

• Added a CONTRIBUTING.md file with contributing guidelines (#183).
• Added clear links to the documentation on minimize_bandwidth, has_bandwidth_k_ordering, and their respective output structs in README.md and docs/src/index.md (#180).
• Updated the GitHub Actions CI workflow to include Julia 1.12 in the testing matrix (#179).
• Added a unit test in test/readme_example.jl to ensure that the example code blocks in README.md and docs/src/index.md (which corresponds to the homepage of the Documenter.jl-generated documentation) align with the actual output of the package on 64-bit architectures (#178, #188).
• Added a Journal of Open Source Software (JOSS) badge to README.md and docs/src/index.md indicating that the package is currently under review by JOSS (#174).

Changed

• Refactored the Basic use examples in the Documenter-generated website into their own Tutorial page (#187, #189).
• Made examples in the docstrings runnable (thus avoiding hardcoding output) by switching from jldoctest to @repl (#176).

v0.2.1

Added

• Added (and compressed) the MatrixBandwidth.jl logo by Rebekka (#162, #165).

Changed

• Edited README.md to better align with a pending submission to the Journal of Open Source Software (#161).
• Reworded/clarified various minor things in several package-wide docstrings (#161).

v0.2.0

Added

• Declared additional unfinished metaheuristic minimization algorithms (PSOHC, AntColony, and TabuSearch) in MatrixBandwidth.Minimization.Metaheuristic (#155).
• Added doctest examples for the minimize_bandwidth and has_bandwidth_k_ordering functions (#154).
• Implemented the Caprara–Salazar-González algorithm (both the minimization solver and the recognition decider), concurrently adding JuMP.jl and HiGHS.jl as notable dependencies for integer linear programming (#137, #149, #152, #156).

Changed

• Switched the default recognition decider from Caprara–Salazar-González to Del Corso–Manzini (#149).
• Added instructions to the documentation for extending the interface with new algorithms via _minimize_bandwidth_impl and _has_bandwidth_k_ordering_impl (#145).
• Renamed _bool_minimal_band_ordering and _bool_bandwidth_k_ordering (the functions wherein new algorithm logic is defined) to _minimize_bandwidth_impl and _has_bandwidth_k_ordering_impl, respectively (#145).
• Split up the @index and @autodocs blocks in the Documenter-generated website by submodule (#144).
• Modified minimize_bandwidth to skip the algorithm call and simply use the original ordering in all cases when bandwidth(A) == bandwidth_lower_bound(A), not just when bandwidth(A) == 0 (#143).
• Removed the export of random_banded_matrix from MatrixBandwidth (#140).
• Exported AbstractAlgorithm and AbstractResult from MatrixBandwidth, and exported their various subtypes from the appropriate submodules (#140).
• Reformatted the export blocks in each submodule to be more in cohesive, similarly to how Graphs.jl does it (#140).
• Removed the leading underscore from many (but not all) top-level utility functions (also renaming _offdiag_nonzero_support to offdiag_nz_support), adding docstrings to all of these (#140).
• Refactored the import structure in submodules to do, e.g., using MatrixBandwidth in favor of a bunch of import ..A, ..B, ..C statements, similarly to how Graphs.jl does it (#140).

Removed

• Removed the empty test suites for the core functions of MatrixBandwidth.Minimization and MatrixBandwidth.Recognition, as minimize_bandwidth and has_bandwidth_k_ordering are already tested via the algorithm-specific test suites (#154).

v0.1.4

Added

• Updated the module docstring and README.md to include a paragraph on the motivation and goals of this package (#131).
• Implemented the Saxe–Gurari–Sudborough algorithm (both the minimization solver and the recognition decider) (#123, #126).
• Added bi_criteria_node_finder (an improvement upon pseudo_peripheral_node_finder) as a new node finder for the heuristic solvers (#112).
• Finished unit tests for all root-level utility functions (#108, #109).
• Added References sections to docstrings for immediate readability in the REPL and in the source code without needing to open the Documenter-generated website (#105).

Changed

• Replaced all deprecated DataStructures.enqueue! and DataStructures.dequeue! calls with Base.push! and Base.popfirst!, respectively (#129).
• Fleshed out and fixed a few typos in the documentation for the Del Corso–Manzini algorithms (#126).
• Renamed the _requires_symmetry internal function (used for input validation) to _requires_structural_symmetry (#123).
• Fleshed out documentation (particularly inline comments) for the Gibbs–Poole–Stockmeyer source code (#116).
• Improved unit tests for the heuristic solvers with more edge cases and scenarios (including the use of custom node finders) (#112).
• Changed the DEFAULT_NODE_FINDER constant for the heuristic solvers from pseudo_peripheral_node_finder to bi_criteria_node_finder (#112).
• Moved the _connected_components function from MatrixBandwidth.Minimization.Heuristic to the root MatrixBandwidth module (specifically src/utils.jl) for universal access (#109).

Fixed

• Tightened the bandwidth_lower_bound function for disconnected graphs by taking the maximum of the bounds computed for each connected component (#124).
• Fixed some test names in the Del Corso–Manzini recognition algorithm test suite ("Bandwidth < k" was meant to be "Bandwidth > k", and "Bandwidth ≥ k" was meant to be "Bandwidth ≤ k") (#123).

v0.1.3

Changed

• Bumped compat for DataStructures.jl from 0.18.15 to 0.18.15 - 0.19 (#100).

(This is a very minor patch only released to bump the DataStructures.jl compat in a timely manner for users.)

v0.1.2

Added

• Started using PrecompileTools.jl to compile all solvers/deciders during package startup, reducing delay on first usage (formerly reached up to ~3 seconds for some algorithms) (#93).
• Created the MatrixBandwidth.ALGORITHMS constant to index all available algorithms by submodule (#93).
• Added "Supertype Hierarchy" sections to the docstrings of all subtypes (both concrete and abstract) (#90).
• Added a section in the MatrixBandwidth module docstring covering practical applications of matrix bandwidth reduction in engineering and scientific computing (#86).

Changed

• Changed some user-facing parameters typed as Int to the more generic Integer (#90).

v0.1.1

Added

• Added the profile function to compute the original profile of a matrix prior to any reordering (#78).
• Added the homepage field to Project.toml to reference the GitHub Pages documentation (#76).
• Created CHANGELOG.md to document changes to this project (#72).
• Clarified certain if-else checks in the bandwidth method and in a helper function for the Del Corso–Manzini Recognition deciders by explaining via inline comments that we cannot reduce over an empty collection (#71).

Changed

• Added PR numbers to changelog entries for better traceability (#73).
• Eliminated unnecessary reallocation of a boolean matrix in the bandwidth method by directly using findall(!iszero, A) instead of calling _offdiag_nonzero_support(A) (#71).
• Switched from a generator comprehension in the bandwidth method to Iterators.map (more idiomatic) (#71).

Fixed

• Changed some blocks enclosed in double backticks to be enclosed in single backticks instead (meant to be rendered as code blocks, not mathematical expressions) (#78).
• Fixed the rendering of the dcm_ps_optimal_depth docstring (#78).
• Updated the compatibility requirements in test/Project.toml to allow only a finite number of breaking releases of Aqua.jl and JET.jl (#74).

v0.1.0

This is the first stable release of MatrixBandwidth.jl, offering unified interfaces for both bandwidth minimization and bandwidth recognition via the minimize_bandwidth and has_bandwidth_k_ordering functions, respectively. Although a few algorithms remain under development, the API is already stable with the bulk of the library already functional and tested. TODO items are clear in the source code as well as documented in the README and the official Documenter-generated website.