Node renumbering is an important step in the solution of sparse systems of equations. It aims to reduce the bandwidth and profile of the matrix. This allows for the speeding up of the solution of the system or allows for the addressing of even larger systems than otherwise would be possible. Research on this topic dates to the late sixties. In most of these algorithms nodal degree is an important consideration. In the new algorithm, we consider the maximum difference in adjacent node numbers as the driving criterion. This new algorithm (IFK), when compared against well-known algorithms such as Reverse-Cuthill-McKee (RCM), Gibbs (GBS), Gibbs-Poole-Stockmeyer (GPS) and Sloan’s (SLN) over 101 test cases from the Boeing-Harwell sparse matrix cases, achieves significant performance improvement in profile and bandwidth reduction and execution time.
Rosen, R. (1968) Matrix Bandwidth Minimization. Proceedings of the 1968 23rd ACM National Conference, Rosenberg, 27-29 August 1968, 585-595. https://doi.org/10.1145/800186.810622
Alway, G.G. (1965) An Algorithm for Re-ducing the Bandwidth of a Matrix of Symmetrical Configuration. The Computer Journal, 8, 264-272. https://doi.org/10.1093/comjnl/8.3.264
Smyth, W.F. (1985) Algorithms for the Reduction of Matrix Bandwidth and Profile. Journal of Computational and Applied Mathematics, 12, 551-561. https://doi.org/10.1016/0377-0427(85)90048-2
Cuthill, E. and McKee, J. (1969) Reducing the Bandwidth of Sparse Symmetric Matrices. Proceedings of the 1969 24th National Conference, New York, 26-28 August 1969, 157-172. https://doi.org/10.1145/800195.805928
George, A. (1971) Computer Implementation of the Finite Element Meth-od. Ph. D Dissertation Tech. Rep. STAN-CS-71-208, Computer Science Department Stanford University.
Liu, W. and Sherman, A.H. (1976) Comparative Analysis of the Cuthill-McKee and the Reverse Cuthill-McKee Ordering Algorithms for Sparse Matrices. SIAM Journal on Numerical Analysis, 13, 198-213. https://doi.org/10.1137/0713020
Gibbs, N.E., Poole, Jr., W.G. and Stockmeyer, P.K. (1976) An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix. SIAM Journal on Numerical Analysis, 13, 236-250. https://doi.org/10.1137/0713023
Sloan, S.W. (1986) An Algorithm for Profile and Wavefront Reduction of Sparse Matrices. International Journal for Numerical Methods in Engineering, 23, 239-251. https://doi.org/10.1002/nme.1620230208
Barnard, S.T., Pothen, A. and Simon, H.D. (1993) A Spectral Algorithm for Envelope Reduction of Sparse Matrices. Proceedings of the 1993 ACM/IEEE Conference on Supercomputing, Portland, 15-19 November 1993, 493-502. https://doi.org/10.1145/169627.169790
Mafteiu-Scai, L.O., Negru, V., Zaharie, D. and Aritoni, O. (2011) Average Bandwidth Reduction in Sparse Matrices Using Hybrid Heuristics. Studia Universitatis Babes-Bolyai, Informatica Vol. LVI No. 3.
