Constructing elimination trees for sparse unsymmetric matrices

Kamer Kaya 1 Bora Uçar 2, 3, 4
2 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : The elimination tree model for sparse unsymmetric matrices and an algorithm for constructing it have been recently proposed [Eisenstat and Liu, SIAM J. Matrix Anal. Appl., 26 (2005) and 29 (2008)]. The construction algorithm has a worst-case time complexity of ${\Theta}(mn)$ for an $n\times n$ unsymmetric matrix having $m$ off-diagonal nonzeros. We propose another algorithm that has a worst-case time complexity of ${\mathcal O}(m\log n)$. 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 proposed one.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00567970
Contributor : Bora Uçar <>
Submitted on : Thursday, October 4, 2012 - 12:34:43 PM
Last modification on : Friday, April 19, 2019 - 3:25:21 PM
Long-term archiving on : Friday, December 16, 2016 - 8:51:06 PM

File

RR-7549.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Kamer Kaya, Bora Uçar. Constructing elimination trees for sparse unsymmetric matrices. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2013, 34 (2), pp.345-354. ⟨10.1137/110825443⟩. ⟨inria-00567970v4⟩

Share

Metrics

Record views

444

Files downloads

971