Abstract
The Reverse Cuthill-McKee (RCM) algorithm is a method for reordering a sparse matrix so that it has a small envelope. Given a starting node, we provide an implementation of the algorithm whose run-time complexity is proved to be linear in the number of nonzeros in the matrix. Numerical experiments are provided which compare the performance of the new implementation to a good conventional implementation.
Similar content being viewed by others
References
C. Berge,The Theory of Graphs and Its Application, John Wiley and Sons, Inc., New York, 1962.
E. Cuthill and J. McKee,Reducing the bandwidth of sparse symmetric matrices, Proc. 24th Nat. Conf., ACM Publ. p. 69, 1122 Ave. of the Americas, New York, N.Y. 1969.
A. George and J. W. H. Liu,Computer Solution of Large Sparse Positive Definite Systems, to be published by Prentice Hall, Inc.
A. George and J. W. H. Liu,An efficient implementation of a pseudoperipheral node finder, ACM Trans. on Math. Software 5 (1979), 284–295.
A. George and J. W. H. Liu,Algorithms for matrix partitioning and the numerical solution of finite element systems, SIAM J. Numer. Anal. 15 (1978), 297–327.
N. E. Gibbs, W. G. Poole, and P. K. Stockmeyer,An algorithm for reducing the bandwidth and profile of a sparse matrix, SIAM J. Numer Anal. 13 (1976), 236–250.
J. W. H. Liu,On reducing the profile of sparse symmetric matrices, Report CS-76-07, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada (February 1976).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Chan, W.M., George, A. A linear time implementation of the reverse Cuthill-McKee algorithm. BIT 20, 8–14 (1980). https://doi.org/10.1007/BF01933580
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01933580