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

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

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

请我喝杯茶吧~

支付宝
微信