Sparsity-Directed Decomposition for Gaussian Elimination on Matrices
- 1 January 1970
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Power Apparatus and Systems
- Vol. PAS-89 (1) , 141-150
- https://doi.org/10.1109/TPAS.1970.292682
Abstract
This is a concise critical survey of the theory and practice relating to the ordered Gaussian elimination on sparse systems. A new method of renumbering by clusters is developed, and its properties described. By establishing a correspondence between matrix patterns and directed graphs, a sequential binary partition is used to decompose the nodes of a graph into clusters. By appropriate ordering of the nodes within each cluster and by selecting clusters, one at a time, both optimal ordering and a useful form of matrix banding are achieved. Some results pertaining to the compatibility between optimal ordering for sparsity and the usual pivoting for numerical accuracy are included.Keywords
This publication has 12 references indexed in Scilit:
- Near-Optimal Ordering of Electronic Circuit EquationsIEEE Transactions on Computers, 1968
- Optimal Power Flow SolutionsIEEE Transactions on Power Apparatus and Systems, 1968
- Semantic Clustering of Index TermsJournal of the ACM, 1968
- The Traveling Salesman Problem: A SurveyOperations Research, 1968
- A Survey of Search TheoryOperations Research, 1968
- Direct solutions of sparse network equations by optimally ordered triangular factorizationProceedings of the IEEE, 1967
- An algorithm for reducing the bandwidth of a matrix of symmetrical configurationThe Computer Journal, 1965
- Techniques for Exploiting the Sparsity or the Network Admittance MatrixIEEE Transactions on Power Apparatus and Systems, 1963
- A graph theoretic approach to matrix inversion by partitioningNumerische Mathematik, 1962
- Dynamic Programming Treatment of the Travelling Salesman ProblemJournal of the ACM, 1962