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

理论学习 / 稀疏矩阵
字数统计: 1.3k   |   阅读时长≈ 6 分钟

本章节介绍 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-2024 Vincere Zhou
  • 访问人数: | 浏览次数:

请我喝杯茶吧~

支付宝
微信