Uma modificação na heurística de Snay para redução do custo computacional do método dos gradientes conjugados ; A modified Snay's heuristic for reducing the computational cost of the preconditioned conjugate gradient method

In this work, a low-cost algorithm for profile reduction is proposed. This algorithm, termed Snay-GL, is based on Snay's heuristic. The resolution of large sparse linear systems is fundamental in several science and engineering applications. Iterative methods are more suitable to solve these linear systems than the direct methods, and the Conjugated Gradient Method (CGM) is a prominent iterative method for solving large sparse linear systems. One can reduce computational costs using this method by applying a local ordering of the vertices of the corresponding graph to improve cache hit rates. This local ordering can be achieved using a heuristic for bandwidth and profile reductions. Several heuristics for profile reduction have been proposed since the 1960s. The results of the new algorithm are compared to the results of heuristics that were selected as potentially being the best low-cost methods for profile reduction. These results were obtained when solving linear systems using the preconditioned conjugate gradient method. Computational experiments confirm a good performance of the proposed reordering algorithm for the considered sets of linear systems. ; Neste trabalho, é proposta uma heurística de baixo custo computacional para redução de profile, baseada na heurística de Snay, e denominada Snay-GL. A resolução de sistemas de equações lineares esparsos e de grande porte é crucial em diversas simulações computacionais nas áreas de ciência e engenharia. Os métodos iterativos são mais adequados para a resolução desses tipos de sistemas, e o Método dos Gradientes Conjugados (MGC) pré-condicionado é um dos métodos iterativos mais proeminentes. Uma localidade de memória adequada favorece a eficiência do MGC pré-condicionado, e essa característica pode ser obtida por ordenações locais geradas por heurísticas para reduções de largura de banda e de profile. Dezenas de heurísticas para redução de profile têm sido propostas desde a década de 1960. A heurística proposta neste trabalho foi comparada com as potenciais ...