A new matrix bandwidth reduction algorithm

The problem that we address is, given a matrix, permute rows and columns so that the bandwidth is minimized. Several constructive heuristic algorithms have been proposed in the literature to reduce the bandwidth of symmetrically structured matrices. However, these methods are often ineffective when applied to some pathological cases. In the present paper we propose a new heuristic obtained as an improvement of the classical Cuthill McKee algorithm. From the computational results it appears that the new algorithm overcomes the pathological cases where the literature algorithm becomes stuck. The algorithm is applied to data from real applications. A comparison on real cases is also made with previous constructive approaches demonstrating the superior performance of the here proposed method.