预排序算法在节点消去中的应用

针对上述算法，已提出了一些改进算法以进一步减少计算量，下面将对这些改进算法进行总结^[18]。受不可区分节点概念^[17]的启发，对最小度算法的第一个改进是采用大规模消去算法，该算法一次可以消去一个子集的节点。如果两个节点x和y满足

Adj（y）∪{y}=Adj（x）∪{x} （4.3）

式中，Adj（y）代表与y相连节点的集合。这样，节点x和节点y就被称为不可区分节点，在排序中可以连续编号。这种做法减少了排序过程中需考虑的节点数目，因为对于不可区分节点集合，只要考虑其中的一个代表性节点就可以了。另外，这种做法可以加速最小度算法中度信息更新步的计算速度，而该步是最小度算法中计算量最大的。采用大规模消去算法，度信息更新只需对代表性节点的度进行更新就可以了。

不完全度信息更新的想法避免了对非最小度节点的度信息更新。在两个节点u和v之间，如果下式成立，则称节点u优先于节点v^[11]

Adj（u）∪{u}⊆Adj（v）∪{v} （4.4）(www.xing528.com)

这样，如果在消去过程中节点u优先于节点v，则在最小度排序算法中节点u先于节点v被消去。因此可以推出，节点v的度信息更新可以在节点u被消去后再进行，这就进一步简化了耗时的度信息更新步。

另一种对最小度算法的改进是在度信息更新步之前消去所有可能的最小度节点。在消去过程中的一个特定步，消去节点y并不会对Adj（y）之外的节点结构产生影响。多重最小度（MMD）算法推迟了消去节点y后的度信息更新，而是在消去所有与节点y度相同的节点后再进行度信息更新。就非零元注入数目来说，这个算法被发现与最小度算法一样好^[30]。此外，还发现MMD算法执行得更快，这是因为能够更早地确认不可区分节点和优先节点，并减少了度信息更新的次数。

在排序算法中，对于给定的指标（度或者非零元注入），经常会出现数值相同的情况，而处理方法通常回归到原始矩阵的自然排序。已经确认，自然排序会对LU分解过程的非零元注入数目和计算时间产生很大影响。因此，在使用排序算法前进行一次快速的预排序是非常可取的。方案0提供了这种预排序的算法，但迄今为止，并没有一种预排序算法适合于所有类型的问题。