Please use this identifier to cite or link to this item:
http://repositorio.ufla.br/jspui/handle/1/55343
Title: | Metaheuristic algorithms for the bandwidth reduction of large-scale matrices |
Keywords: | Bandwidth reduction Heuristics Sparse matrices Reordering algorithms Metaheuristics Graph algorithm Iterated local search Redução da largura de banda Heurística Matrizes esparsas Metaheurísticas Algoritmo de gráfico Algoritmos de reordenação Pesquisa local iterada |
Issue Date: | 2022 |
Publisher: | Springer |
Citation: | OLIVEIRA, S. L. G. de; CARVALHO, C. Metaheuristic algorithms for the bandwidth reduction of large-scale matrices. Journal of Combinatorial Optimization, Boston, v. 43, p. 727–784, 2022. DOI: 10.1007/s10878-021-00801-6. |
Abstract: | This paper considers the bandwidth reduction problem for large-scale sparse matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix. Thus, the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. This manuscript proposes two heuristics for the bandwidth reduction of large-scale matrices. The first is a variant of the Fast Node Centroid Hill-Climbing algorithm, and the second is an algorithm based on the iterated local search metaheuristic. This paper then experimentally compares the solutions yielded by the new reordering algorithms with the bandwidth solutions delivered by state-of-the-art heuristics for the problem, including tests on large-scale problem matrices. A considerable number of results for a range of realistic test problems showed that the performance of the two new algorithms compared favorably with state-of-the-art heuristics for bandwidth reduction. Specifically, the variant of the Fast Node Centroid Hill-Climbing algorithm yielded the overall best bandwidth results. |
URI: | https://doi.org/10.1007/s10878-021-00801-6 http://repositorio.ufla.br/jspui/handle/1/55343 |
Appears in Collections: | DCC - Artigos publicados em periódicos |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
Admin Tools