稀疏矩阵算法最小度数算法六之最小度数算法子程序QMDQT

本章节介绍 the minimum degree algorithm ,我个人将其翻译为最小度数算法。这里我们看最小度数算法的子程序 QMDQT。

QMDQT

(Quotient MD Quotient graph Transformation),这个子程序执行商图的转换,生成相应的 (XADJ, ADJNCY)。新的消除的节点包含节点 ROOT 和 NBRHD 中的节点,在新的商图中生成一个以 ROOT 为代表的新的 supernode ,其在新商图的相邻集合在旧商图的 (RCHSZE, RCHSET) 中。

初始化之后,通过 DO 200 循环,将 (RCHSZE, RCHSET) 中的节点放到 ROOT 中的相邻列表中。如果没有足够的空间,程序会利用 NBRHD 集合中的节点的空间。

在退出之前,通过DO 600 循环将以 ROOT 为代表的相邻节点会加入到 RCHSET 中每一个节点的相邻列表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
C*************************************************************             1.
C************************************************************* 2.
C******* QMDQT ..... QUOT MIN DEG QUOT TRANSFORM ******* 3.
C************************************************************* 4.
C************************************************************* 5.
C 6.
C PURPOSE - THIS SUBROUTINE PERFORMS THE QUOTIENT GRAPH 7.
C TRANSFORMATION AFTER A NODE HAS BEEN ELIMINATED. 8.
C 9.
C INPUT PARAMETERS - 10.
C ROOT - THE NODE JUST ELIMINATED. IT BECOMES THE 11.
C REPRESENTATIVE OF THE NEW SUPERNODE. 12.
C (XADJ, ADJNCY) - THE ADJACENCY STRUCTURE. 13.
C (RCHSZE, RCHSET) - THE REACHABLE SET OF ROOT IN THE 14.
C OLD QUOTIENT GRAPH. 15.
C NBRHD - THE NEIGHBORHOOD SET WHICH WILL BE MERGED 16.
C WITH ROOT TO FORM THE NEW SUPERNODE. 17.
C MARKER - THE MARKER VECTOR. 18.
C 19.
C UPDATED PARAMETER - 20.
C ADJNCY - BECOMES THE ADJNCY OF THE QUOTIENT GRAPH. 21.
C 22.
C************************************************************* 23.
C 24.
SUBROUTINE QMDQT ( ROOT, XADJ, ADJNCY, MARKER, 25.
1 RCHSZE, RCHSET, NBRHD ) 26.
C 27.
C************************************************************* 28.
C 29.
INTEGER ADJNCY(1), MARKER(1), RCHSET(1), NBRHD(1) 30.
INTEGER XADJ(1), INHD, IRCH, J, JSTRT, JSTOP, LINK, 31.
1 NABOR, NODE, RCHSZE, ROOT 32.
C 33.
C************************************************************* 34.
C 35.
IRCH = 0 36.
INHD = 0 37.
NODE = ROOT 38.
100 JSTRT = XADJ(NODE) 39.
JSTOP = XADJ(NODE+1) - 2 40.
IF ( JSTOP .LT. JSTRT ) GO TO 300 41.
C ------------------------------------------------ 42.
C PLACE REACH NODES INTO THE ADJACENT LIST OF NODE 43.
C ------------------------------------------------ 44.
DO 200 J = JSTRT, JSTOP 45.
IRCH = IRCH + 1 46.
ADJNCY(J) = RCHSET(IRCH) 47.
IF ( IRCH .GE. RCHSZE ) GOTO 400 48.
200 CONTINUE 49.
C ---------------------------------------------- 50.
C LINK TO OTHER SPACE PROVIDED BY THE NBRHD SET. 51.
C ---------------------------------------------- 52.
300 LINK = ADJNCY(JSTOP+1) 53.
NODE = - LINK 54.
IF ( LINK .LT. 0 ) GOTO 100 55.
INHD = INHD + 1 56.
NODE = NBRHD(INHD) 57.
ADJNCY(JSTOP+1) = - NODE 58.
GO TO 100 59.
C ------------------------------------------------------- 60.
C ALL REACHABLE NODES HAVE BEEN SAVED. END THE ADJ LIST. 61.
C ADD ROOT TO THE NBR LIST OF EACH NODE IN THE REACH SET. 62.
C ------------------------------------------------------- 63.
400 ADJNCY(J+1) = 0 64.
DO 600 IRCH = 1, RCHSZE 65.
NODE = RCHSET(IRCH) 66.
IF ( MARKER(NODE) .LT. 0 ) GOTO 600 67.
JSTRT = XADJ(NODE) 68.
JSTOP = XADJ(NODE+1) - 1 69.
DO 500 J = JSTRT, JSTOP 70.
NABOR = ADJNCY(J) 71.
IF ( MARKER(NABOR) .GE. 0 ) GO TO 500 72.
ADJNCY(J) = ROOT 73.
GOTO 600 74.
500 CONTINUE 75.
600 CONTINUE 76.
RETURN 77.
END 78.

下面开始逐行解析脚本,首先开始初始化,这里 JSTOP = XADJ(NODE+1) - 2 是将 ROOT 的相邻列表中的最后一个位置空出来不用。如果 JSTOP .LT. JSTRT ,那么说明 ROOT 的相邻列表中只有一个位置,那么要利用其 NBRHD 列表中其它 supernode 的空间,GO TO 300

1
2
3
4
5
6
       IRCH = 0                                                         36.
INHD = 0 37.
NODE = ROOT 38.
100 JSTRT = XADJ(NODE) 39.
JSTOP = XADJ(NODE+1) - 2 40.
IF ( JSTOP .LT. JSTRT ) GO TO 300

下一步我们将 NODE 在旧商图中的相邻集合 RCHSET 中的节点放置到这些位置上。

如果 IRCH .GE. RCHSZE ,那就说明 NODE 的相邻列表空间已经足够存放 RCHSET 中的节点了,不需要利用其 NBRHD 列表中其它节点的空间,那么直接 GO TO 400

1
2
3
4
5
          DO 200 J = JSTRT, JSTOP                                       45.
IRCH = IRCH + 1 46.
ADJNCY(J) = RCHSET(IRCH) 47.
IF ( IRCH .GE. RCHSZE ) GOTO 400 48.
200 CONTINUE 49.

如果 NODE 的空间不够用,那么利用 NBRHD 列表中其它已经消元的 supernode 的空间。

首先LINK = ADJNCY(JSTOP+1) ,将 NODE 相邻列表的最后一个位置设为链接。NODE = - LINK 先将 NODE 设为 - LINK 。如果 LINK 小于 0 ,说明这个位置是一个链接,那么直接 GOTO 100 (这在 ROOT 节点是不可能的,ROOT 节点最后一个位置不可能是链接。这是用于 NBRHD 中的节点的,如果这个节点是一个 supernode ,这些节点最后一个位置可能是链接)。

不然地话,INHD 加1,NODE = NBRHD(INHD) 将 NODE 修改为 NBRHD 的节点。ADJNCY(JSTOP+1) = - NODE 将 ROOT 最后一个位置改为 - NODE,然后GO TO 100 ,利用其空间存放剩余的 RCHSET 中的节点(同样最后一个位置如果已经是链接则继续循环,不然最后一个位置改为链接,放 NBRHD 下一个节点的负数)。

1
2
3
4
5
6
7
300    LINK = ADJNCY(JSTOP+1)                                           53.
NODE = - LINK 54.
IF ( LINK .LT. 0 ) GOTO 100 55.
INHD = INHD + 1 56.
NODE = NBRHD(INHD) 57.
ADJNCY(JSTOP+1) = - NODE 58.
GO TO 100 59.

循环结束之后,RCHSET 中的所有节点均存放好了。

ADJNCY(J+1) = 0 将RCHSET 存放的最后一个位置之后的一个位置设为0,表示RCHSET 节点的终止位置

1
400    ADJNCY(J+1) = 0                                                  64.

反过来,将 RCHSET 中的所有节点的列表中添加 ROOT 节点。

DO 600 循环遍历 RCHSET 的每一个节点,设为 NODE 。如果 NODE 的 MARKER 值低于0,那么说明这个节点已经合并到其它不可区分的节点中了,直接跳过这个节点。不然的话,DO 500 循环遍历 NODE 节点的所有相邻节点,设为 NABOR ;如果 NABOR 的 MARKER 值大于等于0,跳过这个节点。如果 NABOR 的 MARKER 值小于0(如果 NABOR 原来是消元节点,那么就说明 NABOR 和 ROOT 合并了;如果 NABOR 原来是未消元的节点,那么这个节点已经合并到其它不可区分的节点中了。无论是哪种情况,此时这个 NABOR 都可以修改了),那么将其修改为 ROOT ,然后跳出循环, GO TO 600 ,运行下一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
       DO 600 IRCH = 1, RCHSZE                                          65.
NODE = RCHSET(IRCH) 66.
IF ( MARKER(NODE) .LT. 0 ) GOTO 600 67.
JSTRT = XADJ(NODE) 68.
JSTOP = XADJ(NODE+1) - 1 69.
DO 500 J = JSTRT, JSTOP 70.
NABOR = ADJNCY(J) 71.
IF ( MARKER(NABOR) .GE. 0 ) GO TO 500 72.
ADJNCY(J) = ROOT 73.
GOTO 600 74.
500 CONTINUE 75.
600 CONTINUE 76.
RETURN 77.
END 78.

其实,这里只将第一个可以修改的节点中改为 ROOT ,就完成了添加 ROOT 节点的任务,实际上此时 NODE 的 商图相邻位点中可能有重复的 ROOT 节点或其它可以删除的位点(MARKER 值小于0)。

以下图从 的形成过程中,节点 8 原始相邻节点为 5,3,6,9,按照上面的脚本遍历,第一个相邻节点 5 的 MARKER 值为 -1,改为 6 ,然后退出循环,因此节点 8 修改后的相邻列表实际为 6,3,6,9,存在重复的 ROOT 节点 6,并不是下面的 3,6,9 。

74

参考文献

  1. George A, Liu J, Ng E. Computer solution of sparse linear systems[J]. Oak Ridge National Laboratory, 1994.
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2019-2022 Vincere Zhou
  • 访问人数: | 浏览次数:

请我喝杯茶吧~

支付宝
微信