Uma avaliação de heurísticas para redução de largura de banda de matrizes

Abstract

Computational cost of a linear system solver can be reduced by matrix bandwidth reduction. Bandwidth reduction consists of carrying out permutations of lines and columns so that they allow coefficients to remain near the main diagonal. By a systematic review, eight heuristics were identified with the best benefits, i.e., bandwidth reduction per computational cost, and then were implemented. In addition, the GPS heuristic, one of the most known heuristic in this problem, was implemented. Furthermore, two new heuristics are proposed in this work. Computational simulations were performed with these 11 heuristics in 113 instances of the Harwell-Boeing Sparse Matrix Collection and with three sets of instances with linear systems obtained from discretizations of the heat conduction and the Laplace equations by finite volumes. These linear systems were solved using the preconditioned Conjugate Gradient Method. According to the results presented here, the best heuristic in the simulations performed with the Harwell-Boeing Sparse Matrix Collection was the Variable neighborhood search for bandwidth reduction. However, this heuristic is not indicated to reduce the computational cost of preconditioned Conjugate Gradient Method in large-scale sparse linear systems. In particular, the better results in reducing the computational cost of solving linear systems were obtained by low-cost heuristics. Then, low-cost heuristics can be considered the best option to reduce the computational cost of the preconditioned Conjugate Gradient Method.