Um algoritmo pseudo-periférico genérico para a heurı́stica de Snay

Abstract

A resolução de sistemas de equações lineares na forma Ax = b é fundamental em muitas simulações numéricas na ciência e na engenharia. A redução do profile de A pode reduzir o custo de armazenamento e de resolução desses sistemas. Neste trabalho, propõe-se um algoritmo genérico para encontrar vértices pseudo-periféricos para a heurı́stica de Snay. Em testes em oito instâncias da base de matrizes esparsas Harwell-Boeing, verificou-se que o número de vértices pseudo-periféricos selecionados pela heurı́stica de Snay pode ser adequado para instâncias pequenas, mas é insuficiente para se obter bons resultados em instâncias que não são pequenas. Com os testes, mostra-se que é recomendável selecionar até 16% de vértices pseudo-periféricos em relação ao tamanho da instância.