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

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.