An Implementation of Tarjan's Algorithm for the Block Triangularization of a Matrix

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Implementation of Tarjan's Algorithm for the Block Triangularization of a Matrix

Full text

Pdf (618 KB)

Source

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

Pages: 137 - 147

Year of Publication: 1978

ISSN:0098-3500

Authors

I. S. Duff	Computer Science and Systems Division, Building 8.9, AERE Harwell, Didcot, Oxfordshire, OX11 ORA, England
J. K. Reid	Computer Science and Systems Division, Building 8.9, AERE Harwell, Didcot, Oxfordshire, OX11 ORA, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 139, Citation Count: 12

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/355780.355785 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	DUFF, I S. Analysis of sparse systems. D.Phil. Th., Oxford U., Oxford, 1972.
	2	DUFF, I.S. On permutations to block triangular form. J. Inst. Math. Appl. 19 (1977),{ 339-342.
	3	DUFF, I.S. On algorithms for obtaining a maximal transversal. To appear.
	4	DUFF, I.S. A survey of sparse matrix research. Proc. IEEE 65 (1977), 500-535.
	5	I. S. Duff , J. K. Reid, Algorithm 529: Permutations To Block Triangular Form [F1], ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.189-192, June 1978 [doi>10.1145/355780.355790]
	6	GUSTAVSON, F.G. Finding the block lower triangular form of a sparse matrix. In Sparse Matrix Computations, Bunch and Rose, Eds., Academic Press, New York, 1976.
	7	HARARY, F. A graph theoretic method for the complete reduction of a matrix with a view toward finding the eigenvalues. J. Math. Phys. ~8, (1959), 104-111.
	8	MUNRO, I. Efficient determination of the transitive closure of a directed graph. Inform. Proc. Left. I, (1971), 56-58.
	9	MUNRO, I. Some results in the study of algorithms. Tech. Rep 32, Dept. of Comptr. SEN., U. of Toronto, Toronto, 1971.
	10	RYDER, B.G. The Fortran verifier: user's guide. Comptg. Sci. Tech. Rep. 12, Bell Telephone Labs., Murray Hill, N.J., 1973.
	11	SARGENT, R.W.H., AND WESTERBERG, A.W. "Speed-up" m chemical engineering design. Trans. Inst. Chem. Engrs. }t2, (1964), 190-197.
	12	STEWARD, D.V Partitioning and tearing systems of equations. SIAM J. Numer. Anal. ~, (1965 ), 345-365.
	13	TARJAN, R.E. Depth first search and linear graph algorithms. SIAM J. Comptg. 1, (1972), 146-160.
	14	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]

CITED BY 12

	David Marple, A hierarchy preserving hierarchical compactor, Proceedings of the 27th ACM/IEEE conference on Design automation, p.375-381, June 24-27, 1990, Orlando, Florida, United States
	I. S. Duff , J. K. Reid, Some Design Features of a Sparse Matrix Code, ACM Transactions on Mathematical Software (TOMS), v.5 n.1, p.18-35, March 1979
	I. S. Duff, On Algorithms for Obtaining a Maximum Transversal, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.315-330, Sept. 1981
	Alex Pothen , Chin-Ju Fan, Computing the block triangular form of a sparse matrix, ACM Transactions on Mathematical Software (TOMS), v.16 n.4, p.303-324, Dec. 1990
	I. S. Duff , J. K. Reid, Algorithm 529: Permutations To Block Triangular Form [F1], ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.189-192, June 1978
	I. S. Duff , J. K. Reid, The design of MA48: a code for the direct solution of sparse unsymmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.187-226, June 1996
	Patrick P. A. Storms , J. Bernard van Veelen , Erik Boasson, A Process Distribution Approach for Multisensor Data Fusion Systems Based on Geographical Dataspace Partitioning, IEEE Transactions on Parallel and Distributed Systems, v.16 n.1, p.14-23, January 2005
	I. S. Duff , A. M. Erisman , C. W. Gear , J. K. Reid, Sparsity structure and Gaussian elimination, ACM SIGNUM Newsletter, v.23 n.2, p.2-8, April 1988
	Eduardo Cattani , Alicia Dickenstein, Counting solutions to binomial complete intersections, Journal of Complexity, v.23 n.1, p.82-107, February, 2007
	Jonas Larsson, A Framework for Implementation-Independent Simulation Models, Simulation, v.82 n.9, p.563-579, September 2006
	Jostein R. Natvig , Knut-Andreas Lie, Fast computation of multiphase flow in porous media by implicit discontinuous Galerkin schemes with optimal ordering of elements, Journal of Computational Physics, v.227 n.24, p.10108-10124, December, 2008
	Ivana Pultarová, Iterative aggregation: disaggregation methods and ordering algorithms, Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools, October 20-24, 2008, Athens, Greece