Skip to main content
Log in

A linear time implementation of the reverse Cuthill-McKee algorithm

  • Part I Computer Science
  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. C. Berge,The Theory of Graphs and Its Application, John Wiley and Sons, Inc., New York, 1962.

    Google Scholar 

  2. 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.

    Google Scholar 

  3. A. George and J. W. H. Liu,Computer Solution of Large Sparse Positive Definite Systems, to be published by Prentice Hall, Inc.

  4. A. George and J. W. H. Liu,An efficient implementation of a pseudoperipheral node finder, ACM Trans. on Math. Software 5 (1979), 284–295.

    Google Scholar 

  5. 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.

    Google Scholar 

  6. 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.

    Google Scholar 

  7. 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).

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01933580

Keywords

Navigation