Bandwidth and Profile Reduction of Sparse Matrices: An Experimental Comparison of New Heuristics

The problem of sparse matrix bandwidth reduction is addressed and solved with two approaches suitable for both symmetric and non-symmetric matrices. The former is a constructive method, the latter is an application of a metaheuristic scheme. This heuristic algorithm has been implemented on parallel machines. Both approaches are compared with previous methods in the literature (suited only for symmetric cases). Benchmarks on real industrial cases, show the superior effectiveness and efficiency of the proposed methods. Some results illustrating the parallel performance of the parallel heuristic are also reported. The extension of the proposed algorithms to the profile minimization problem is presented. 1 Introduction The use of numerical techniques is the core of many scientific studies. In a large number of cases, the bottleneck of numerical methods is the solution of sparse linear systems, often repeated many times for different right-hand sides. In this paper, we study a problem stri..