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.

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.

Publication Type:	Conference Paper
URI:	http://researchrepository.murdoch.edu.au/id/eprint/27380

Item Control Page

Downloads