A New Heuristic for Bandwidth and Profile Reductions of Matrices Using a Self-organizing Map

In this work, a heuristic for bandwidth and profile reductions of symmetric and asymmetric matrices using a one-dimensional self-organizing map is proposed. Experiments and comparisons of results obtained were performed in relation to results of the Variable neighborhood search for bandwidth reduction. Simulations with these two heuristics were performed with 113 instances of the Harwell-Boeing sparse matrix collection and with 2 sets of instances with linear systems composed of sparse symmetric positive-definite matrices. The linear systems were solved using the Jacobi-preconditioned Conjugate Gradient Method. According to the results presented here, the best heuristic in the simulations performed was the Variable neighborhood search for bandwidth reduction. On the other hand, when the vertices of the corresponding graph were originally ordered in a sequence given by a space-filling curve, no gain was obtained when applying a heuristic for reordering the graph vertices.