Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Another algorithm for reducing bandwidth and profile of a sparse matrix

Smyth, W.F. and Arany, I. (1976) Another algorithm for reducing bandwidth and profile of a sparse matrix. In: National Computer Conference (AFIPS '76), 7 - 10 June 1976, New York pp. 987-994.

PDF - Published Version
Download (770kB)
Link to Published Version:
*Subscription may be required


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.

Item Type: Conference Paper
Item Control Page Item Control Page


Downloads per month over past year