稀疏矩阵算法最小度数算法五之最小度数算法子程序QMDRCH

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

QMDRCH

(Quotient MD Reachable set) ,这个子程序用于查找一个给定节点 ROOT 通过已经消元的节点的 reachable set 。这里使用的相邻结构必须已经是之前提到的商图结构。

输出的 reachable set 存储在向量 RCHSET 中,其大于为 RCHSZE 。作为一个副产品,邻近 ROOT 的已经消元的 supernode 放在 NBRHD 中,其大小为 NHDSZE 。则两个集合中的节点其 MARKER 值均会设为非零值。

这个子程序完全就是之前提到的算法的实现,如下图。

1

脚本如下:

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
79
80
81
82
C***************************************************************           1.
C*************************************************************** 2.
C********* QMDRCH ..... QUOT MIN DEG REACH SET ********** 3.
C*************************************************************** 4.
C*************************************************************** 5.
C 6.
C PURPOSE - THIS SUBROUTINE DETERMINES THE REACHABLE SET OF 7.
C A NODE THROUGH A GIVEN SUBSET. THE ADJACENCY STRUCTURE 8.
C IS ASSUMED TO BE STORED IN A QUOTIENT GRAPH FORMAT. 9.
C 10.
C INPUT PARAMETERS - 11.
C ROOT - THE GIVEN NODE NOT IN THE SUBSET. 12.
C (XADJ, ADJNCY) - THE ADJACENCY STRUCTURE PAIR. 13.
C DEG - THE DEGREE VECTOR. DEG(I) LT 0 MEANS THE NODE 14.
C BELONGS TO THE GIVEN SUBSET. 15.
C 16.
C OUTPUT PARAMETERS - 17.
C (RCHSZE, RCHSET) - THE REACHABLE SET. 18.
C (NHDSZE, NBRHD) - THE NEIGHBORHOOD SET. 19.
C 20.
C UPDATED PARAMETERS - 21.
C MARKER - THE MARKER VECTOR FOR REACH AND NBRHD SETS. 22.
C GT 0 MEANS THE NODE IS IN REACH SET. 23.
C LT 0 MEANS THE NODE HAS BEEN MERGED WITH 24.
C OTHERS IN THE QUOTIENT OR IT IS IN NBRHD SET. 25.
C 26.
C*************************************************************** 27.
C 28.
SUBROUTINE QMDRCH ( ROOT, XADJ, ADJNCY, DEG, MARKER, 29.
1 RCHSZE, RCHSET, NHDSZE, NBRHD ) 30.
C 31.
C*************************************************************** 32.
C 33.
INTEGER ADJNCY(1), DEG(1), MARKER(1), 34.
1 RCHSET(1), NBRHD(1) 35.
INTEGER XADJ(1), I, ISTRT, ISTOP, J, JSTRT, JSTOP, 36.
1 NABOR, NHDSZE, NODE, RCHSZE, ROOT 37.
C 38.
C*************************************************************** 39.
C 40.
C ----------------------------------------- 41.
C LOOP THROUGH THE NEIGHBORS OF ROOT IN THE 42.
C QUOTIENT GRAPH. 43.
C ----------------------------------------- 44.
NHDSZE = 0 45.
RCHSZE = 0 46.
ISTRT = XADJ(ROOT) 47.
ISTOP = XADJ(ROOT+1) - 1 48.
IF ( ISTOP .LT. ISTRT ) RETURN 49.
DO 600 I = ISTRT, ISTOP 50.
NABOR = ADJNCY(I) 51.
IF ( NABOR .EQ. 0 ) RETURN 52.
IF ( MARKER(NABOR) .NE. 0 ) GO TO 600 53.
IF ( DEG(NABOR) .LT. 0 ) GO TO 200 54.
C ------------------------------------- 55.
C INCLUDE NABOR INTO THE REACHABLE SET. 56.
C ------------------------------------- 57.
RCHSZE = RCHSZE + 1 58.
RCHSET(RCHSZE) = NABOR 59.
MARKER(NABOR) = 1 60.
GO TO 600 61.
C ------------------------------------- 62.
C NABOR HAS BEEN ELIMINATED. FIND NODES 63.
C REACHABLE FROM IT. 64.
C ------------------------------------- 65.
200 MARKER(NABOR) = -1 66.
NHDSZE = NHDSZE + 1 67.
NBRHD(NHDSZE) = NABOR 68.
300 JSTRT = XADJ(NABOR) 69.
JSTOP = XADJ(NABOR+1) - 1 70.
DO 500 J = JSTRT, JSTOP 71.
NODE = ADJNCY(J) 72.
NABOR = - NODE 73.
IF (NODE) 300, 600, 400 74.
400 IF ( MARKER(NODE) .NE. 0 ) GO TO 500 75.
RCHSZE = RCHSZE + 1 76.
RCHSET(RCHSZE) = NODE 77.
MARKER(NODE) = 1 78.
500 CONTINUE 79.
600 CONTINUE 80.
RETURN 81.
END 82.

现在开始逐行分析脚本。

DO 600 会遍历 ROOT 在商图中的相邻节点,如果相邻节点 NABOR 为0,说明已经到了相邻列表的终点 。如果相邻节点 NABOR 的 MARKER 值不为0,说明这个节点合并到其它节点中或者已经在 reachable set 中了,因此直接跳过这个节点,GO TO 600

如果相邻节点 NABOR 的 DEG 值低于0,说明这个节点是已经消除的 supernode, 那么 GO TO 200 ,将 NABOR 节点的相邻节点加到 reachable set 中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
C        -----------------------------------------                        41.
C LOOP THROUGH THE NEIGHBORS OF ROOT IN THE 42.
C QUOTIENT GRAPH. 43.
C ----------------------------------------- 44.
NHDSZE = 0 45.
RCHSZE = 0 46.
ISTRT = XADJ(ROOT) 47.
ISTOP = XADJ(ROOT+1) - 1 48.
IF ( ISTOP .LT. ISTRT ) RETURN 49.
DO 600 I = ISTRT, ISTOP 50.
NABOR = ADJNCY(I) 51.
IF ( NABOR .EQ. 0 ) RETURN 52.
IF ( MARKER(NABOR) .NE. 0 ) GO TO 600 53.
IF ( DEG(NABOR) .LT. 0 ) GO TO 200 54.

如果 NABOR 的 MARKER 值为 0,并且 DEG 值大于等于0,那么就直接将 NABOR 加入到 reachable set 中,最后将其 MARKER 值改为 1,然后 GO TO 600

1
2
3
4
5
6
7
C                    -------------------------------------                55.
C INCLUDE NABOR INTO THE REACHABLE SET. 56.
C ------------------------------------- 57.
RCHSZE = RCHSZE + 1 58.
RCHSET(RCHSZE) = NABOR 59.
MARKER(NABOR) = 1 60.
GO TO 600 61.

接下来是 GO TO 200 之后的语句,需要将 NABOR 节点的相邻节点加到 reachable set 中。

将 NABOR 加入到 NBRHD 中,并将其 MARKER 值改为 -1(因为这些节点会合并到 ROOT 中,因此属于要合并的节点,其 MARKER 值改为负数) 。

JSTRT 和 JSTOP 是 NABOR 的相邻列表的第一个位置和最后一个位置。注意这里 NABOR 是已经消元的 supernode ,其在商图中的相邻列表如果不够放,最后一个位置会是链接(负数),最后一个相邻位点之后一个位置为 0 。

因此,IF (NODE) 300, 600, 400 ,这是一条算术 IF 语句,会判断 NODE 的符号,根据算术表达式的结果来决定程序执行的转移,如果 NODE < 0 ,则 GO TO 300 ,此时 NODE 是下一个节点的链接,NABOR = - NODE ,继续遍历相邻节点 ; 如果 NODE = 0 ,则 GO TO 600 ,说明此时已经找完所有相邻节点; 如果 NODE > 0 则 GO TO 400,正常向下运行 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
C                 -------------------------------------                   62.
C NABOR HAS BEEN ELIMINATED. FIND NODES 63.
C REACHABLE FROM IT. 64.
C ------------------------------------- 65.
200 MARKER(NABOR) = -1 66.
NHDSZE = NHDSZE + 1 67.
NBRHD(NHDSZE) = NABOR 68.
300 JSTRT = XADJ(NABOR) 69.
JSTOP = XADJ(NABOR+1) - 1 70.
DO 500 J = JSTRT, JSTOP 71.
NODE = ADJNCY(J) 72.
NABOR = - NODE 73.
IF (NODE) 300, 600, 400 74.
400 IF ( MARKER(NODE) .NE. 0 ) GO TO 500 75.
RCHSZE = RCHSZE + 1 76.
RCHSET(RCHSZE) = NODE 77.
MARKER(NODE) = 1 78.
500 CONTINUE 79.
600 CONTINUE 80.
RETURN 81.
END 82.

参考文献

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

请我喝杯茶吧~

支付宝
微信