稀疏矩阵算法最小度数算法七之最小度数算法子程序QMDUPD

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

QMDUPD

(Quotient MD UPDate),这个子程序用于执行自由度更新这一步。节点的新的自由度通过 (NLIST, LIST) 来确定。这个子程序同时会确定不可区分的节点。

第一个循环 DO 200 之后调用子程序 QMDMRG 来确定不可区分的节点,它们会合并到一块,并且更新这些节点的自由度。

对于没有合并的节点,DO 600 循环通过调用子程序 QMDRCH 来确定它们新的自由度。

向量 RCHSET 和 NBRHD 用于作为临时向量。

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
C****************************************************************          1.
C**************************************************************** 2.
C********** QMDUPD ..... QUOT MIN DEG UPDATE *********** 3.
C**************************************************************** 4.
C**************************************************************** 5.
C 6.
C PURPOSE - THIS ROUTINE PERFORMS DEGREE UPDATE FOR A SET 7.
C OF NODES IN THE MINIMUM DEGREE ALGORITHM. 8.
C 9.
C INPUT PARAMETERS - 10.
C (XADJ, ADJNCY) - THE ADJACENCY STRUCTURE. 11.
C (NLIST, LIST) - THE LIST OF NODES WHOSE DEGREE HAS TO 12.
C BE UPDATED. 13.
C 14.
C UPDATED PARAMETERS - 15.
C DEG - THE DEGREE VECTOR. 16.
C QSIZE - SIZE OF INDISTINGUISHABLE SUPERNODES. 17.
C QLINK - LINKED LIST FOR INDISTINGUISHABLE NODES. 18.
C MARKER - USED TO MARK THOSE NODES IN REACH/NBRHD SETS. 19.
C 20.
C WORKING PARAMETERS - 21.
C RCHSET - THE REACHABLE SET. 22.
C NBRHD - THE NEIGHBORHOOD SET. 23.
C 24.
C PROGRAM SUBROUTINES - 25.
C QMDMRG. 26.
C 27.
C**************************************************************** 28.
C 29.
SUBROUTINE QMDUPD ( XADJ, ADJNCY, NLIST, LIST, DEG, 30.
1 QSIZE, QLINK, MARKER, RCHSET, NBRHD ) 31.
C 32.
C**************************************************************** 33.
C 34.
INTEGER ADJNCY(1), LIST(1), DEG(1), MARKER(1), 35.
1 RCHSET(1), NBRHD(1), QSIZE(1), QLINK(1) 36.
INTEGER XADJ(1), DEG0, DEG1, IL, INHD, INODE, IRCH, 37.
1 J, JSTRT, JSTOP, MARK, NABOR, NHDSZE, NLIST, 38.
1 NODE, RCHSZE, ROOT 39.
C 40.
C**************************************************************** 41.
C 42.
C ------------------------------------------------ 43.
C FIND ALL ELIMINATED SUPERNODES THAT ARE ADJACENT 44.
C TO SOME NODES IN THE GIVEN LIST. PUT THEM INTO 45.
C (NHDSZE, NBRHD). DEG0 CONTAINS THE NUMBER OF 46.
C NODES IN THE LIST. 47.
C ------------------------------------------------ 48.
IF ( NLIST .LE. 0 ) RETURN 49.
DEG0 = 0 50.
NHDSZE = 0 51.
DO 200 IL = 1, NLIST 52.
NODE = LIST(IL) 53.
DEG0 = DEG0 + QSIZE(NODE) 54.
JSTRT = XADJ(NODE) 55.
JSTOP = XADJ(NODE+1) - 1 56.
DO 100 J = JSTRT, JSTOP 57.
NABOR = ADJNCY(J) 58.
IF ( MARKER(NABOR) .NE. 0 .OR. 59.
1 DEG(NABOR) .GE. 0 ) GO TO 100 60.
MARKER(NABOR) = - 1 61.
NHDSZE = NHDSZE + 1 62.
NBRHD(NHDSZE) = NABOR 63.
100 CONTINUE 64.
200 CONTINUE 65.
C -------------------------------------------- 66.
C MERGE INDISTINGUISHABLE NODES IN THE LIST BY 67.
C CALLING THE SUBROUTINE QMDMRG. 68.
C -------------------------------------------- 69.
IF ( NHDSZE .GT. 0 ) 70.
1 CALL QMDMRG ( XADJ, ADJNCY, DEG, QSIZE, QLINK, 71.
1 MARKER, DEG0, NHDSZE, NBRHD, RCHSET, 72.
1 NBRHD(NHDSZE+1) ) 73.
C ---------------------------------------------------- 74.
C FIND THE NEW DEGREES OF THE NODES THAT HAVE NOT BEEN 75.
C MERGED. 76.
C ---------------------------------------------------- 77.
DO 600 IL = 1, NLIST 78.
NODE = LIST(IL) 79.
MARK = MARKER(NODE) 80.
IF ( MARK .GT. 1 .OR. MARK .LT. 0 ) GO TO 600 81.
MARKER(NODE) = 2 82.
CALL QMDRCH ( NODE, XADJ, ADJNCY, DEG, MARKER, 83.
1 RCHSZE, RCHSET, NHDSZE, NBRHD ) 84.
DEG1 = DEG0 85.
IF ( RCHSZE .LE. 0 ) GO TO 400 86.
DO 300 IRCH = 1, RCHSZE 87.
INODE = RCHSET(IRCH) 88.
DEG1 = DEG1 + QSIZE(INODE) 89.
MARKER(INODE) = 0 90.
300 CONTINUE 91.
400 DEG(NODE) = DEG1 - 1 92.
IF ( NHDSZE .LE. 0 ) GO TO 600 93.
DO 500 INHD = 1, NHDSZE 94.
INODE = NBRHD(INHD) 95.
MARKER(INODE) = 0 96.
500 CONTINUE 97.
600 CONTINUE 98.
RETURN 99.
END 100.

下面开始逐行分析脚本

首先查找与给定列表中节点相邻的已经消元的 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
       IF ( NLIST .LE. 0 )  RETURN                                      49.
DEG0 = 0 50.
NHDSZE = 0 51.
DO 200 IL = 1, NLIST 52.
NODE = LIST(IL) 53.
DEG0 = DEG0 + QSIZE(NODE) 54.
JSTRT = XADJ(NODE) 55.
JSTOP = XADJ(NODE+1) - 1 56.
DO 100 J = JSTRT, JSTOP 57.
NABOR = ADJNCY(J) 58.
IF ( MARKER(NABOR) .NE. 0 .OR. 59.
1 DEG(NABOR) .GE. 0 ) GO TO 100 60.
MARKER(NABOR) = - 1 61.
NHDSZE = NHDSZE + 1 62.
NBRHD(NHDSZE) = NABOR 63.
100 CONTINUE 64.
200 CONTINUE 65.

通过调用子程序 QMDMRG 来找到 LIST 中的不可区分的节点并进行合并,并更新其 DEG 值。

运行结束后,不可区分的supernode 的 MARKER 值为 2,被合并的节点的 MARKER 值为 -1

1
2
3
4
    IF ( NHDSZE .GT. 0 )                                             70.
1 CALL QMDMRG ( XADJ, ADJNCY, DEG, QSIZE, QLINK, 71.
1 MARKER, DEG0, NHDSZE, NBRHD, RCHSET, 72.
1 NBRHD(NHDSZE+1) ) 73.

对于那些没有合并的节点,更新其 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
C        ----------------------------------------------------             74.
C FIND THE NEW DEGREES OF THE NODES THAT HAVE NOT BEEN 75.
C MERGED. 76.
C ---------------------------------------------------- 77.
DO 600 IL = 1, NLIST 78.
NODE = LIST(IL) 79.
MARK = MARKER(NODE) 80.
IF ( MARK .GT. 1 .OR. MARK .LT. 0 ) GO TO 600 81.
MARKER(NODE) = 2 82.
CALL QMDRCH ( NODE, XADJ, ADJNCY, DEG, MARKER, 83.
1 RCHSZE, RCHSET, NHDSZE, NBRHD ) 84.
DEG1 = DEG0 85.
IF ( RCHSZE .LE. 0 ) GO TO 400 86.
DO 300 IRCH = 1, RCHSZE 87.
INODE = RCHSET(IRCH) 88.
DEG1 = DEG1 + QSIZE(INODE) 89.
MARKER(INODE) = 0 90.
300 CONTINUE 91.
400 DEG(NODE) = DEG1 - 1 92.

如果 NBRHD 不为空,将其中节点的 MARKER 值重置为 0 。

这样就将上面调用 QMDRCH 修改的 MARKER 值全部重置了。

1
2
3
4
5
6
7
8
             IF ( NHDSZE .LE. 0 )  GO TO 600                            93.
DO 500 INHD = 1, NHDSZE 94.
INODE = NBRHD(INHD) 95.
MARKER(INODE) = 0 96.
500 CONTINUE 97.
600 CONTINUE 98.
RETURN 99.
END 100.

最后,只有 NLIST 中节点(即要消元节点的相邻节点)的 MARKER 值被修改了,被合并到不可区分的 supernode 中的节点为 -1,其它为 2

参考文献

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

请我喝杯茶吧~

支付宝
微信