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

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.