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

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

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

请我喝杯茶吧~

支付宝
微信