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 symmetrica lly structured matrices. However, these methods are often ineffective when applied to some pathological cases. In the present paper we propose a new h euristic obtained as an improvement of the classical Cuthill McKee algorith m. From the computational results it appears that the new algorithm overcom es the pathological cases where the literature algorithm get stuck. The alg orithm is applied to data from real applications. A comparison on real case s is also made with previous constructive approaches demonstrating the supe rior performance of the here proposed method. (C) 1998 Elsevier Science B.V . All rights reserved.