Um análise comparativa entre quatro algoritmos para reduções de largura de banda de matrizes

Autores

  • Sanderson L. Gonzaga de Oliveira
  • Guilherme O. Chagas

DOI:

https://doi.org/10.5540/03.2018.006.02.0422

Palavras-chave:

Matrizes esparsas, algoritmos em grafos, redução de largura de banda, teoria dos grafos, renumeração de vértices.

Resumo

Neste trabalho, é relatado um experimento computacional com o objetivo de comparar quatro algoritmos heurísticos que podem ser considerados, em diferentes situações, os principais m´etodos em redução de largura de banda de matrizes. Foi publicado, recentemente, o algoritmo Dual Representation Simulated Annealing para redução de largura de banda de matrizes. Os resultados desse algoritmo superaram os resultados de outro algoritmo, baseado na metaheurística Variable Neighborhood Search, considerada pelos autores como o método no estado da arte anterior no problema. Neste contexto, as heurísticas devem apresentar custo de execução muito baixo, pois são utilizadas para acelerar resolutores de sistemas de equações lineares. Entretanto, em geral, algoritmos baseados em meta-heurísticas são lentos e não são eficazes nesse problema de otimização combinatória, mesmo quando aplicados em instâncias pequenas. Neste trabalho, comparamos resultados do algoritmo Dual Representation Simulated Annealing com resultados do método Reverse Cuthill–McKee, uma variação desse método e uma variação da busca em largura, que foram consideradas, recentemente, as três heurísticas de baixo custo de execução mais promissoras no problema de redução de largura de banda, para diferentes áreas de aplicação. Baseados nos resultados de nossos experimentos, consideramos que essas três heurísticas de baixo custo de processamento superam o algoritmo Dual Representation Simulated Annealing, quando o tempo de execução é uma variável considerada na comparação.

Downloads

Não há dados estatísticos.

Downloads

Publicado

2019-01-21

Edição

Seção

Trabalhos Completos