Constructing Elimination Trees for Sparse Unsymmetric Matrices
Constructing Elimination Trees for Sparse Unsymmetric Matrices
复制标题
构造稀疏非对称矩阵的消除树
DOI：
--
复制
发表时间：
2013
影响因子：
1.5
通讯作者：
B. Uçar
中科院分区：
文献类型：
--
作者：
K. Kaya;B. Uçar
Eisenstat和Liu [SIAM J. Matrix Anal.应用程序、第26（2005）号决议，第26页。686- 705]和[SIAM J. Matrix Anal.应用程序、29（2008），pp. 1363- 1381]。构造算法的最坏情况时间复杂度为${Theta}（mn）$， imes n$非对称矩阵，具有$m$非对角非零值。我们提出了另一种算法，具有最坏情况下的时间复杂度为${mathcal O}（mlog n）$。我们比较了这两种算法的实验，并表明这两种算法是有效的。Eisenstat和Liu的算法在许多实际情况下更快，但在某些情况下，两种算法的运行时间之间存在显着差异，有利于本文提出的算法。
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 ${Theta}(mn)$ for an $n imes n$ unsymmetric matrix having $m$ off-diagonal nonzeros. We propose another algorithm that has a worst-case time complexity of ${mathcal O}(mlog 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 one proposed here.