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