Use este identificador para citar ou linkar para este item: http://repositorio.ufla.br/jspui/handle/1/29261
Título: Uma revisão de heurísticas para renumeração de vértices para redução do custo de execução do método GMRES pré-condicionado
Autor : Carvalho, Cláudio Vinícius de
Lattes: http://lattes.cnpq.br/6463072364110494
Primeiro orientador: Oliveira, Sanderson L. Gonzaga de
Primeiro membro da banca: Brandão, Diego Nunes
Segundo membro da banca: Resende, Antônio Maria Pereira de
Palavras-chave: Generalized Minimal Residual (GMRES)
Pré-condicionadores
Renumerações de vértices
Heurísticas
Preconditioning
Vertices renumbering
Heuristics
Iterated Local Search
Computação - Matemática
Computer - Mathematics
Data da publicação: 16-Abr-2018
Referência: CARVALHO, C. V. de. Uma revisão de heurísticas para renumeração de vértices para redução do custo de execução do método GMRES pré-condicionado. 2018. 126 p. Dissertação (Mestrado em Ciência da Computação)–Universidade Federal de Lavras, Lavras, 2018.
Resumo: Sistemas de equações lineares envolvendo matrizes esparsas de grande porte surgem, geralmente, da discretização de equações diferenciais parciais, comuns em simulações computacionais de várias áreas da ciência. Métodos iterativos, como o Generalized Minimal Residual (GMRES) pré-condicionado, são os mais adequados para resolução desses sistemas. Quando se utiliza esses métodos, pode-se obter redução de seu custo computacional ao se aplicar técnicas de redução de largura de banda ou de profile nas matrizes envolvidas. Essas técnicas consistem em agrupar os coeficientes não nulos da matriz o mais próximo possível da diagonal principal por meio de permutações de suas linhas e colunas. Neste trabalho, avaliou-se o desempenho de métodos heurísticos no estado da arte para redução de largura de banda ou de profile no contexto de resolução de sistemas de equações lineares com o método GMRES pré-condicionado. Ainda, uma heurística baseada na meta-heurística Iterated Local Search para os problemas de redução de largura de banda e de profile de matrizes foi proposta. Nos testes realizados em 172 instâncias da base SuiteSparse Matrix Collection a heurística proposta apresentou bons resultados, principalmente na redução de profile de matrizes assimétricas e de banda de matrizes simétricas. Contudo, seu alto tempo de execução não a qualificou como heurística propícia para reduzir o custo computacional do GMRES pré-condicionado. Treze métodos heurísticos foram avaliados nos experimentos para redução do custo de execução do GMRES pré-condicionado. Foram considerados seis pré-condicionadores, baseados em fatoração incompleta (ILUT, ILUC, ILU(k), VBILUT e VBILUK) e em multigrid (ARMS) em 20 instâncias de grandes dimensões. As simulações apontaram, em consonância com a literatura, que os melhores resultados na redução do custo computacional de sistemas de equações lineares são obtidos por heurísticas com baixo custo computacional, mesmo que não apresentem grandes reduções de largura de banda ou profile. Ainda, constatou-se que, para certas instâncias, nenhuma heurística contribuiu para a redução do custo de resolução dos sistemas com o GMRES pré-condicionado.
Abstract: Systems of linear equations that involve large sparse matrices arising from the discretization of partial differential equations are commonplace in computational simulations from many scientific fields. Iterative methods such as the preconditioned Generalized Minimal Residual method (GMRES) are the most suitable for solving such systems. When these methods are used, one can achieve computational cost reductions by applying bandwidth and profile reduction techniques on the related matrices. The purpose of these techniques is to group the coefficients of the matrix near to the main diagonal by applying a sequence of permutations of its rows and columns. In this work, the performance of heuristic methods for bandwidth and profile reductions was evaluated when used alongside the preconditioned GMRES method for solving linear systems. Furthermore, we propose a heuristic method for bandwidth and profile reductions based on the metaheuristic Iterated Local Search. In the tests carried in 172 instances from the SuiteSparse Matrix Collection, the proposed algorithm showed good results, especially in reducing the bandwidth of symmetric matrices and reducing the profile of unsymmetric matrices. However, due to its high execution times, it was not considered conducive to reduce the execution time of the preconditioned GMRES. Thirteen heuristic methods were evaluated in the experiments with the preconditioned GMRES. Six preconditioners based on incomplete factorization (ILUT, ILUC, ILU(k), VBILUT and VBILUK) and on multigrid methods (ARMS) were used, in 20 large instances. In line with previous works, heuristic methods with low computational cost obtained the best results in reducing the computational cost of solving linear systems in the simulations conducted, even though the bandwidth and profile reductions they provide are not the best overall. More, it was observed that for certain instances no heuristic was able to help in reducing the computational cost of solving linear systems with preconditioned GMRES.
URI: http://repositorio.ufla.br/jspui/handle/1/29261
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.