Another algorithm for reducing bandwidth and profile of a sparse matrix

ABSTRACT

The paper describes a new bandwidth reduction method for sparse matrices which promises to be both fast and effective in comparison with known methods. The algorithm operates on the undirected graph corresponding to the incidence matrix induced by the original sparse matrix, and separates into three distinct phases: (1) determination of a spanning tree of maximum length, (2) modification of the spanning tree into a free level structure of small width, (3) level-by-level numbering of the level structure. The final numbering produced corresponds to a renumbering of the rows and columns of a sparse matrix so as to concentrate non-zero elements of the matrix in a band about the main diagonal.

REFERENCES

• 1: Willoughby, Ralph A., Sparse Matrix Algorithms and Their Relation to Problem Classes and Computer Architecture, IBM Research Publication RC 2833, March 1970, 38 pp.
• 2: Udo W. Pooch , Al Nieder, A Survey of Indexing Techniques for Sparse Matrices, ACM Computing Surveys (CSUR), v.5 n.2, p.109-133, June 1973 [doi>10.1145/356616.356618]
• 3: Tewarson, R. P., "Computations with Sparse Matrices," SIAM Review, 12--4, October 1970, pp. 527--543.
• 4: Curtis, A. R. and J. K. Reid, "The Solution of Large Sparse Unsymmetric Systems of Linear Equations," Proc. IFIP Congress 71, 1972, pp. 1240--1245.
• 5: E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
• 6: Rose, D. J., Symmetric Elimination on Sparse Positive Definite Systems and the Potential Flow Network Problem. Ph.D. thesis, Harvard Univ., 1972.
• 7: Arany, Ilona, W. F. Smyth and Lajos Szóda, "An Improved Method for Reducing the Bandwidth of Sparse Symmetric Matrices," Proc. IFIP Congress 71, 1972, pp. 1246--1250.
• 8: Smyth, W. F. and W. M. L. Benzi, "An Algorithm for Finding the Diameter of a Graph," Proc. IFIP Congress 74, 1975, pp. 500--503.
• 9: Gibbs, Norman E., William G. Poole and Paul K. Stockmeyer, An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix, Technical Report No. 5, July 1974, 25 pp.
• 10: Arany, Ilona and Lajos Szóda, "Ritka Szimmetrikus Matrixok Sávszélesség Redukciója, "Információ Elektronika 4, 1973, pp. 273--282.