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

• Ano de defesa: 2016
• Autor(a) principal: Bernardes, Júnior Assis Barreto
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Lavras; Programa de Pós-Graduação em Ciência da Computação; UFLA; brasil; Departamento de Ciência da Computação
• Palavras-chave em Português: Redução de profile; Heurísticas; Método dos gradientes conjugados precondicionado; Matrizes esparsas; Profile reduction; Heuristics; Preconditioned conjugate gradient method; Sparce matrices; Ciência da Computação
• Link de acesso: http://repositorio.ufla.br/jspui/handle/1/11482

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.