Conference paper
Another algorithm for reducing bandwidth and profile of a sparse matrix
Proceedings of the June 7-10, 1976, national computer conference and exposition on - AFIPS '76, pp.987-994
National Computer Conference (AFIPS '76) (New York, 07/06/1976–10/06/1976)
1976
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.
Details
- Title
- Another algorithm for reducing bandwidth and profile of a sparse matrix
- Authors/Creators
- W.F. Smyth (Author/Creator)I. Arany (Author/Creator)
- Publication Details
- Proceedings of the June 7-10, 1976, national computer conference and exposition on - AFIPS '76, pp.987-994
- Conference
- National Computer Conference (AFIPS '76) (New York, 07/06/1976–10/06/1976)
- Identifiers
- 991005541768007891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference paper
Metrics
252 File views/ downloads
129 Record Views