Please use this identifier to cite or link to this item: http://repositorio.ufla.br/jspui/handle/1/29261
Title: 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
Authors: Oliveira, Sanderson L. Gonzaga de
Brandão, Diego Nunes
Resende, Antônio Maria Pereira de
Keywords: 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
Issue Date: 16-Apr-2018
Publisher: Universidade Federal de Lavras
Citation: 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.
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
Appears in Collections:Ciência da Computação - Mestrado (Dissertações)



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.