Level-based heuristics and hill climbing for the antibandwidth maximization problem

The antibandwidth maximization problem aims to maximize the minimum distance of entries of a sparse symmetric matrix from the diagonal and as such may be regarded as the dual of the well-known bandwidth minimization problem. In this paper, we consider the feasibility of adapting heuristic algorithms for the bandwidth minimization problem to the antibandwidth maximization problem. In particular, using an inexpensive level-based heuristic, we obtain an initial ordering that we refine using a hill-climbing algorithm. This approach performs well on matrices coming from a range of practical problems with an underlying mesh. Comparisons with existing approaches show that, on this class of problems, our algorithm can be competitive with recently reported results in terms of quality while being significantly faster and applicable to much larger problems. Copyright (c) 2012 John Wiley & Sons, Ltd.