本章节介绍 the minimum degree algorithm ,我个人将其翻译为最小度数算法。这里我们看最小度数算法的子程序 QMDUPD 。
QMDUPD
(Quotient MD UPDate),这个子程序用于执行自由度更新这一步。节点的新的自由度通过 (NLIST, LIST) 来确定。这个子程序同时会确定不可区分的节点。
第一个循环 DO 200
之后调用子程序 QMDMRG 来确定不可区分的节点,它们会合并到一块,并且更新这些节点的自由度。
对于没有合并的节点,DO 600
循环通过调用子程序 QMDRCH 来确定它们新的自由度。
向量 RCHSET 和 NBRHD 用于作为临时向量。
1 | C**************************************************************** 1. |
下面开始逐行分析脚本
首先查找与给定列表中节点相邻的已经消元的 supernodes ,将它们放在 **(NHDSZE, NBRHD)**中,DEG0 表示 LIST 中的节点数目(包括其不可区分的节点)。
DO 100
循环中的 IF 判断就是说,NABOR 节点需要满足 DEG 值小于 0 (表示其为消元节点) 并且 Marker 值等于0(表示其为除了本次需要消元的节点形成的 supernode 之外的其它已经消元的 supernode),将这样的 NABOR 节点的 MARKER 值设为 -1(这里设为 -1 应该只是为了去重,下面调用 QMDMRG 会将其MARKER 值重新设为 0 ) ,放到 (NHDSZE, NBRHD) 中。
1 | IF ( NLIST .LE. 0 ) RETURN 49. |
通过调用子程序 QMDMRG 来找到 LIST 中的不可区分的节点并进行合并,并更新其 DEG 值。
运行结束后,不可区分的supernode 的 MARKER 值为 2,被合并的节点的 MARKER 值为 -1。
1 | IF ( NHDSZE .GT. 0 ) 70. |
对于那些没有合并的节点,更新其 DEG 值,为 。
DO 600
遍历 LIST 中的每一个节点 NODE ,其 MARKER 值为 MARK 。如果 MARK 大于 1 (新合并的 supernode 的代表节点)或者小于 0(新合并的 supernode 的其它节点),那么跳过这个节点。
不然的话,接着往下走,将 NODE 的 MARKER 值设为 2,调用 QMDRCH ,注意 QMDRCH 子程序中加入到 RCHSET 的节点其 MARKER 值必须为 0 ,因此此时 RCHSET 中的节点均不在 NLIST 中,均为新的其它未消元的节点。将 DEG0 赋值给 DEG1 ,通过DO 300
循环将 RCHSET 的节点数目加入到 DEG1 ,然后将 NODE 的 DEG 值设为 DEG1 - 1(DEG0 中包含 NODE 本身)。
同样地,此时 NHDSZE 中的节点均不是与本次要消元的节点相邻的已消元的 supernode ,均为新的其它与已消元的节点不相邻的 supernode 。
1 | C ---------------------------------------------------- 74. |
如果 NBRHD 不为空,将其中节点的 MARKER 值重置为 0 。
这样就将上面调用 QMDRCH 修改的 MARKER 值全部重置了。
1 | IF ( NHDSZE .LE. 0 ) GO TO 600 93. |
最后,只有 NLIST 中节点(即要消元节点的相邻节点)的 MARKER 值被修改了,被合并到不可区分的 supernode 中的节点为 -1,其它为 2 。
参考文献
- George A, Liu J, Ng E. Computer solution of sparse linear systems[J]. Oak Ridge National Laboratory, 1994.