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.
*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.
|Publication Type:||Conference Paper|
|Item Control Page|
Downloads per month over past year