dissertação
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
Carregando...
Notas
Data
Autores
Orientadores
Editores
Coorientadores
Membros de banca
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Lavras
Faculdade, Instituto ou Escola
Departamento
Departamento de Ciência da Computação
Programa de Pós-Graduação
Ciência da Computação
Agência de fomento
Tipo de impacto
Áreas Temáticas da Extenção
Objetivos de Desenvolvimento Sustentável
Dados abertos
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.
Descrição
Área de concentração
Agência de desenvolvimento
Palavra chave
Marca
Objetivo
Procedência
Impacto da pesquisa
Resumen
ISBN
DOI
Citação
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.