Back to Search
Start Over
CONSTRUCTING ELIMINATION TREES FOR SPARSE UNSYMMETRIC MATRICES.
- Source :
-
SIAM Journal on Matrix Analysis & Applications . 2013, Vol. 34 Issue 2, p345-354. 10p. - Publication Year :
- 2013
-
Abstract
- The elimination tree model for sparse unsymmetric matrices and an algorithm for constructing it have been recently proposed by Eisenstat and Liu [SIAM J. Matrix Anal. Appl., 26 (2005), pp. 686-705] and [SIAM J. Matrix Anal. Appl., 29 (2008), pp. 1363-1381]. The construction algorithm has a worst-case time complexity of Θ(mn) for an n X n unsymmetric matrix having m off-diagonal nonzeros. We propose another algorithm that has a worst-case time complexity of ...(mlogn). We compare the two algorithms experimentally and show that both algorithms are efficient in general. The algorithm of Eisenstat and Liu is faster in many practical cases, yet there are instances in which there is a significant difference between the running time of the two algorithms in favor of the one proposed here. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954798
- Volume :
- 34
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Matrix Analysis & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 91878998
- Full Text :
- https://doi.org/10.1137/110825443