Uma avaliação da utilização de busca local com o método Reverse Cuthill-McKee

Abstract

 Com reduções de largura de banda e de profile de matrizes, pode-se obter redução no custo de processamento de resolutores iterativos de sistemas de equações lineares (SELs). O método Reverse Cuthill-McKee é um algoritmo clássico para redução de largura de banda e de profile. Esse método apresenta baixo custo computacional e gera resultados razoáveis. Neste trabalho, é avaliada a busca local Hill-Climbing para se melhorar os resultados do método Reverse Cuthill-McKee, ao iniciar seu processamento com vértices pseudo-periféricos determinados pelo algoritmo de George-Liu. Não foram observadas melhorias nos resultados com a busca local. Também, constatou-se que o custo de processamento exigido pela busca local não compensa eventuais melhorias nos resultados obtidos nas reduções de largura de banda e de profile. Consequentemente, não há redução do custo de processamento na resolução de sistemas de equações lineares pelo método dos gradientes conjugados.