A probabilistic approach to optimal pivoting and prediction of fill-in for random sparse matrices
- 1 July 1972
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuit Theory
- Vol. 19 (4) , 329-336
- https://doi.org/10.1109/tct.1972.1083477
Abstract
In a previous work by the authors, a deterministic approach was used to evaluate the sparse-matrix technique for solving a large system of equationAX = b. In this paper, a probabilistic approach is used to further study the sparse-matrix technique. Analytic expressions for both the most probable number of fill-ins and the most probable optimal pivot for minimum fill-in in random sparse matrices has been obtained. Probabilistic prediction is also made for the fill-in, as well as the upper bound of the fill-in for randomly generated sparse matrices.Keywords
This publication has 10 references indexed in Scilit:
- On Optimal-Pivoting Algorithms in Sparse MatricesIEEE Transactions on Circuit Theory, 1972
- The Sparse Tableau Approach to Network Analysis and DesignIEEE Transactions on Circuit Theory, 1971
- Effective Ordering of Sparse Matrices Arising from Nonlinear Electrical NetworksIEEE Transactions on Circuit Theory, 1971
- An Optimal Ordering of Electronic Circuit Equations for a Sparse Matrix SolutionIEEE Transactions on Circuit Theory, 1971
- ON DIRECT METHODS FOR SOLVING SYMMETRIC SYSTEMS OF LINEAR EQUATIONSPublished by Defense Technical Information Center (DTIC) ,1969
- The Product Form of Inverses of Sparse Matrices and Graph TheorySIAM Review, 1967
- Direct solutions of sparse network equations by optimally ordered triangular factorizationProceedings of the IEEE, 1967
- On the Product Form of Inverses of Sparse MatricesSIAM Review, 1966
- Techniques for Exploiting the Sparsity or the Network Admittance MatrixIEEE Transactions on Power Apparatus and Systems, 1963
- The Elimination form of the Inverse and its Application to Linear ProgrammingManagement Science, 1957