An approximate minimum degree ordering algorithm
An approximate minimum degree ordering algorithm
复制标题
DOI：
10.1137/s0895479894278952
复制
发表时间：
1996-10-01
影响因子：
1.5
通讯作者：
Duff, IS
中科院分区：
文献类型：
--
作者：
Amestoy, PR;Davis, TA;Duff, IS
提出了一种近似最小度排序算法，用于在数值分解之前对对称稀疏矩阵进行预排序，我们使用基于商图的技术进行矩阵分解，使我们能够获得最小度的计算廉价界。我们证明了这些边界通常等于实际的度。结果算法通常比以前的最小度排序算法快得多，并且产生的结果在质量上与其他最小度算法的最佳排序相当。
An approximate minimum degree (AMD) ordering algorithm for preordering a symmetric sparse matrix prior to numerical factorization is presented, We use techniques based on the quotient graph for matrix factorization that allow us to obtain computationally cheap bounds for the minimum degree. We show that these bounds are often equal to the actual degree. The resulting algorithm is typically much faster than previous minimum degree ordering algorithms and produces results that are comparable in quality with the best orderings from other minimum degree algorithms.