A Comparison of Several Bandwidth and Profile Reduction Algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Comparison of Several Bandwidth and Profile Reduction Algorithms

Full text

Pdf (566 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 2 , Issue 4 (December 1976) table of contents

Pages: 322 - 330

Year of Publication: 1976

ISSN:0098-3500

Authors

Norman E. Gibbs	Department of Mathematics, College of William and Mary, Williamsburg, WA
William G. Poole, Jr.	Department of Mathematics, College of William and Mary, Williamsburg, WA
Paul K. Stockmeyer	Department of Mathematics, College of William and Mary, Williamsburg, WA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 143, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/355705.355707 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BOLSTAD, J.H., LEAF, G.K., LINDEMAN, A J., AND KAPER, H.G. An empirical investigation of reordering and datu management for finite element systems of equations. Rep. ANL- 8056, Argonne Nat. Lab , Argonne, Ill., 1973
	2	CHENG, K.Y. Minimizing the bandwidth of sparse symmetric matrices. Computing 11 (1973), 103-110.
	3	COLLINS, R.J. Bandwidth reduction by automatm renumbering. Int J. Numer. Methods E?~grg. 6 (1973), 345-356
	4	CVTHIL~, E H Several strategies for reducmg the bandwidth of matrices In Sparse Matmces and Their Applications, D.J. Rose and R.A Willoughby, Eds., Plenum Press, New York, 1972
	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	EVEI~STINE, G.C Recent ~mprovements to BANDIT. In NASTRAN" Users' Experience, NASA TMX-3278, NASA, Washington, D.C., Sept. 1975, pp. 511-521.
	7	GEORGE, J.A. Computer implementation of the finite element method. Tech. Rep. STAN- CS-71-208, Com ptr. Sci. Dep, Stanford U., Stanford, Calif., 1971.
	8	GIBBS, N E., POOLE, W G., JR., AND STOCKMEYER, P.K. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM J. Numer. Analyszs 13, 2 (April 1976), 235-251
	9	KING, I.P. An automatic reordering scheme for simultaneous equations derived from network systems. Int. J. Numer. Methods Engrg. 2 (1970), 523-533.
	10	LIU, W , AND SHERMAN, A H. Comparative analysis of the Cuthill-McKee and the reverse Cuthlll-McKee ordering algorithms for sparse matrices. SIAM J. Numer. Analysis 18, 2 (April 1976), 197-213.
	11	Paul Tiing Renn Wang, Bandwidth minimization, reducibility decomposition, and triangularizationof sparse matrices., 1973

CITED BY 11

	Wei Li, Compiler cache optimizations for banded matrix problems, Proceedings of the 9th international conference on Supercomputing, p.21-30, July 03-07, 1995, Barcelona, Spain
	H. L. Crane, Jr. , Norman E. Gibbs , William G. Poole, Jr. , Paul K. Stockmeyer, Algorithm 508: Matrix Bandwidth and Profile Reduction [F1], ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.375-377, Dec. 1976
	Rami G. Melhem , K. V. S. Ramarao, Multicolor reordering of sparse matrices resulting from irregular grids, ACM Transactions on Mathematical Software (TOMS), v.14 n.2, p.117-138, June 1988
	John G. Lewis, Algorithm 582: The Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms for Reordering Sparse Matrices, ACM Transactions on Mathematical Software (TOMS), v.8 n.2, p.190-194, June 1982
	Robert Niewiadomski , José Nelson Amaral , Robert C. Holte, A performance study of data layout techniques for improving data locality in refinement-based pathfinding, Journal of Experimental Algorithmics (JEA), v.9 n.es, 2004
	John G. Lewis, Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms, ACM Transactions on Mathematical Software (TOMS), v.8 n.2, p.180-189, June 1982
	Norman E. Gibbs, Algorithm 509: A Hybrid Profile Reduction Algorithm [F1], ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.378-387, Dec. 1976
	Yihua Bai , Wilfried N. Gansterer , Robert C. Ward, Block tridiagonalization of "effectively" sparse symmetric matrices, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.326-352, September 2004
	Anshul Gupta , Vipin Kumar , Ahmed Sameh, Performance and Scalability of Preconditioned Conjugate Gradient Methods on Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.6 n.5, p.455-469, May 1995
	Ye Chen , Dmitry Pavlov , John F. Canny, Large-scale behavioral targeting, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
	Alberto Caprara , Juan-José Salazar-González, Laying Out Sparse Graphs with Provably Minimum Bandwidth, INFORMS Journal on Computing, v.17 n.3, p.356-373, Summer 2005