Use este identificador para citar ou linkar para este item: http://repositorio.ufla.br/jspui/handle/1/11482
Título: Uma modificação na heurística de Snay para redução do custo computacional do método dos gradientes conjugados
Título(s) alternativo(s): A modified Snay's heuristic for reducing the computational cost of the preconditioned conjugate gradient method
Autor : Bernardes, Júnior Assis Barreto
Lattes: http://lattes.cnpq.br/0542528320586819
Primeiro orientador: Oliveira, Sanderson L. Gonzaga de
Primeiro membro da banca: Andrade, Alessandro Vivas
Segundo membro da banca: Assis, Luciana Pereira de
Palavras-chave: Redução de profile
Heurísticas
Método dos gradientes conjugados precondicionado
Matrizes esparsas
Profile reduction
Heuristics
Preconditioned conjugate gradient method
Sparce matrices
Data da publicação: 1-Ago-2016
Referência: BERNARDES, J. A. B. Uma modificação na heurística de Snay para redução do custo computacional do método dos gradientes conjugados. 2016. 155 p. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal de Lavras, Lavras, 2016.
Resumo: 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 melhores heurísticas para redução de profile selecionadas em revisão sistemática. As comparações foram realizadas em relação à redução do custo computacional do MGC pré-condicionado pelo método de Jacobi e pela fatoração incompleta de Cholesky, em quatro conjuntos de instâncias. Os experimentos computacionais realizados neste trabalho confirmam uma bom desempenho da heurística Snay-GL proposta neste trabalho.
Abstract: 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.
URI: http://repositorio.ufla.br/jspui/handle/1/11482
Publicador: Universidade Federal de Lavras
Idioma: por
Aparece nas coleções:DCC - Ciência da Computação - Mestrado (Dissertações)



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.