Modification of the minimum-degree algorithm by multiple elimination
Modification of the minimum-degree algorithm by multiple elimination
复制标题
DOI：
10.1145/214392.214398
复制
发表时间：
1985-06
期刊：
影响因子：
--
通讯作者：
Joseph W. H. Liu
中科院分区：
文献类型：
--
作者：
Joseph W. H. Liu
在稀疏矩阵计算中减少填充和操作的最广泛使用的订购方案是最低级算法。这里引入了多重消除的概念，以修改常规方案。使用K-BY-K网格模型问题讨论动机。实验结果表明，修改后的版本保留了（通常比）原始订购算法的填充属性，但需要更少的计算机时间。订购时间的减少取决于问题，并且对于某些问题，修改后的算法可以比最低学位算法的现有实现快几倍。还引入了算法中外部学位的使用。
The most widely used ordering scheme to reduce fills and operations in sparse matrix computation is the minimum-degree algorithm. The notion of multiple elimination is introduced here as a modification to the conventional scheme. The motivation is discussed using the k-by-k grid model problem. Experimental results indicate that the modified version retains the fill-reducing property of (and is often better than) the original ordering algorithm and yet requires less computer time. The reduction in ordering time is problem dependent, and for some problems the modified algorithm can run a few times faster than existing implementations of the minimum-degree algorithm. The use of external degree in the algorithm is also introduced.