Reducing the total bandwidth of a sparse unsymmetric matrix

Abstract. For a sparse symmetric matrix, there has been much attention given to algorithms for reducing the bandwidth. As far as we can see, little has been done for the unsymmetric matrix A, which has distinct lower and upper bandwidths l and u. When Gaussian elimination with row interchanges is applied, the lower bandwidth is unaltered, while the upper bandwidth becomes l+u. With column interchanges, the upper bandwidth is unaltered, while the lower bandwidth becomes l+ u. We therefore seek to reduce min(l, u) + l+ u, which we call the total bandwidth. We compare applying the reverse Cuthill–McKee algorithm to A+AT, to the row graph of A, and to the bipartite graph of A. We also propose an unsymmetric variant of the reverse Cuthill–McKee algorithm. In addition, we have adapted the node-centroid and hill-climbing ideas of Lim, Rodrigues, and Xiao to the unsymmetric case. We have found that using these to refine a Cuthill–McKee-based ordering can give significant further bandwidth reductions. Numerical results for a range of practical problems are presented and comparisons made with the recent lexicographical method of Baumann, Fleischmann, and Mutzbauer