Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices

In this paper we examine the Cuthill–McKee algorithm for ordering the unknowns and equations in systems of linear equations, A x = b, where A is sparse, symmetric, and positive definite. This algorithm is designed to produce a permutation matrix P such that PAPT has a small bandwidth. If we wish to exploit zeros in the band of A which occur before the first nonzero in each row and column, it has been experimentally observed that reversing the ordering produced by the Cuthill–McKee algorithm is often very much better than the original ordering in terms of the amount of storage and work required to factor A. We prove that for band elimination methods, the two orderings are equivalent and that, surprisingly, the reverse ordering is always at least as good as the original one when envelope elimination techniques are used. We give a condition on the matrix A under which the reverse ordering is strictly better than the original one, and we include several numerical experiments and analyses of practical examples to illustrate our results.