A New Node Centroid Algorithm for Bandwidth Minimization

1 Introduction

For a symmetric matrix A = { aij}, the matrix band­ width minimization problem is to find a permutation of rows and columns of the matrix A so as to bring all the non-zero elements of A to reside in a band that is as close as possible to the main diagonal, that is to Minimize{max{li- Jl : aij =/:- 0} }. The band­ width minimization problem also can be stated in the context of graph as: Let G(V, E) be a graph on n vertices. Label all vertices with different labels from the set 1, 2, ... , n so that f(v) is the label for vertex v. Then, with the bandwidth of G defined to be BJ(G) = Max{if(u)- f(v)l : Vu,Vv,(u,v) E E(G)} , the bandwidth minimization problem is to find a label­ ing, f , which minimizes BJ(G). Note, that we transform a graph bandwidth problem into a matrix bandwidth problem by using its incidence matrix.The bandwidth minization problem was proved to be NP-complete by Papadimitriou [Papadimitriou, 1976] .

Many heuristic algorithms have been proposed in solv­ ing the bandwidth minimization problem, considering its importance. In 1969, the classical CM [Cuthill et al., 1969] algorithm appeared, which used Breadth-First

Brian Rodrigues

School of Business Singapore Management University, 469 Bukit Timah Road Singapore 259756 br@smu.edu.sg

Fei Xiao

School of Computing National University of Singapore 3 Science Drive 2 Singapore 117543 xiaofei@comp.nus.edu.sg

Search to construct a level structure of the graph. The GPS algorithm [Gibbs et al., 1976], which is also based on the level structure, can obtain almost the same result as the CM algorithm, but about eight times faster than the CM algorithm. Esposito et al. [Esposito et al., 1998] proposed a new WBRA(Wonder Bandwidth Reduction Algorithm), which can achieve better result than the classical CM and GPS algorithm. Marti et al. [Marti et al., 2001] proposed a new Tabu Search method in which candidate list strategy was used to accelerate the selection of move in a neighborhood. Extensive Experi­ mentation showed that their Tabu Search O\ltperformed best-known algorithms in terms of solution quality. Re­ cently, Pinana et al. [Pinana et al., 2001] used a GRASP (Greedy Randomized Adaptive Search Procedure) with Path Relinking method for the problem. Computational Results showed that the GRASP with Path Relinking achieved the best solution in quality, though it is slower than the Tabu Search.

We have proposed a new NCHC algorithm (Node Cen­ troid method with Hill-Climbing) to solve the bandwidth minimization problem. Experimentation shows that our NCHC algorithm has outperformed other heuristic algo­ rithm on the solution quality. Meanwhile the fast version of our new NCHC algorithm is comparable with CM and GPS algorithm on speed, which is about 100 times faster than the newly developed Tabu Search and GRASP with Path Relinking. In next Section we present the general framework of the algorithm. Computational Results are reported in Section 3. Finally, we draw our conclusion and provide some directions for future research.

2 The Node Centroid with Hill-Climbing algorithm

The Node Centroid method with Hill Climbing (NCHC) employs the strategy of using the Node Centroid method for global search with Hill-Climbing in local search. An initial labeling is generated by performing Breadth-First Search (BFS) on the given graph representation of the matrix with random start vertex. We then use the Node Centroid method to adjust vertices to a central ( cen­ troid) position among its neighbors. From this, a new labeling is created on which we perform Hill Climbing to obtain local optima. The Node Centroid method and Hill Climbing iterate a number of times, following which a new initial labeling is generated by BFS. The entire process is repeated several times within the NCHC al­ gorithm which is described in Algorithm 1 given below:

In the algorithm, the NC component comprises of Node Centroid labeling adjustments and HC denotes Hill Climbing. These will be described in more detail in the following sections. The HC procedure is invoked only every other time we perform the NC since it is the bottleneck for the speed of the algorithm and since ex­ perimentation has shown that this frequency proportion works well.

3 Computational Results

We have compared our new NCHC algorithm with algorithms developed by other re­ searchers on three sets of test cases from the Harwell-Boeing Sparse Matrix Collection (http:/ /math.nist.gov /MatrixMarket/data/Harwell­ Boeing/) of standard test matrices, which represent a large spectrum of scientific and engineering applications. vVe have also developed a fast version of our NCHC algorithm, denoted FNCHC.

The first two test sets have also been used in [Pinana et al., 2001]. Experimental results are shown in Table 1

As shown in table 1, the best solution in quality has been obtained by our NCHC, which is also much faster than the newly developed GRASP _PR. Our FNCHC has achieved very good solution in a short time, which is more than 100 times faster than the TS and GRASP _PR. Though our FNCHC is slower than the GPS algorithm but it obtained solution 37% and 47% better than the classical GPS algorithm. We also compare our approach with the Esposito's WBRA and TS [Esposito et al., 1998] on the DWT test set from the Harwell-Boeing Sparse Matrix Collection, where our new NCHC also get the best results, and our FNCHC obtain better result than the WBRA and TS in a short time.

4 Conclusions

We have proposed a Node Centroid adjustment method with Hill Climbing for the well-known matrix bandwidth minimization problem. Experimentation has shown that the Node Centroid global search works well with Hill Climbing for this problem. Best solutions in quality are achieved by the new NCHC algorithm, while the FNCHC provides good solution quality at fast speeds and is comparable in speed to the fast GPS algorithm.lt also indicates that we can apply the new Node Centroid procedure to other similar combinatorial optimization problems, such as matrix profile reduction and Minimum Linear Arrangement Problem in the future.