Uma modificação na heurística de Snay para redução do custo computacional do método dos gradientes conjugados

Neste trabalho, e proposta uma heuristica de baixo custo computacional para reducao de profile, baseada na heuristica de Snay, e denominada Snay-GL. A resolucao de sistemas de equacoes lineares esparsos e de grande porte e crucial em diversas simulacoes computacionais nas areas de ciencia e engenharia. Os metodos iterativos sao mais adequados para a resolucao desses tipos de sistemas, e o Metodo dos Gradientes Conjugados (MGC) pre-condicionado e um dos metodos iterativos mais proeminentes. Uma localidade de memoria adequada favorece a eficiencia do MGC pre-condicionado, e essa caracteristica pode ser obtida por ordenacoes locais geradas por heuristicas para reducoes de largura de banda e de profile. Dezenas de heuristicas para reducao de profile tem sido propostas desde a decada de 1960. A heuristica proposta neste trabalho foi comparada com as potenciais melhores heuristicas para reducao de profile selecionadas em revisao sistematica. As comparacoes foram realizadas em relacao a reducao do custo computacional do MGC pre-condicionado pelo metodo de Jacobi e pela fatoracao incompleta de Cholesky, em quatro conjuntos de instâncias. Os experimentos computacionais realizados neste trabalho confirmam uma bom desempenho da heuristica Snay-GL proposta neste trabalho.