Metaheuristic-based Heuristics for Symmetric-matrix Bandwidth Reduction: A Systematic Review

Computational and storage costs of resolution of large sparse linear systems Ax = b can be performed by reducing the bandwidth of A. Bandwidth reduction consists of carrying out permutations of lines and columns so that they allow coefficients to remain near the main diagonal.When considering an adjacency matrix of a graph, bandwidth reduction can be considered in the sense of modifying the order in which the graph vertices are numbered. Heuristics for bandwidth reduction are revised in this study, aiming at determining which of them offers the higher bandwidth reduction with a reasonable computational cost. Specifically, metaheuristic-based heuristics are reviewed in this systematic review. Moreover, 29 metaheuristic-based heuristics tested for bandwidth reduction were found. Among them, 4 are recommended as possible state-of-the-art heuristics for addressing the problem.