1C ======================================================================
2C === Fortran AMD demo main program ====================================
3C ======================================================================
4
5C ----------------------------------------------------------------------
6C AMD, Copyright (c) by Timothy A. Davis, Patrick R.
7C Amestoy, and Iain S. Duff.  See ../README.txt for License.
8C email: DrTimothyAldenDavis@gmail.com
9C ----------------------------------------------------------------------
10
11C A simple Fortran 77 main program that illustrates the use of the
12C Fortran version of AMD (both the AMD and AMDBAR routines).  Note
13C that aggressive absorption has no effect on this particular matrix.
14
15C       AP and AI contain the symmetric can_24 Harwell/Boeing matrix,
16C       including upper and lower triangular parts, but excluding the
17C       diagonal entries.  Note that this matrix is 1-based, with row
18C       and column indices in the range 1 to N.
19
20        INTEGER N, NZ, IWLEN, PFREE, I, J, K, JNEW, P, INEW,
21     $      METHOD, NCMPA
22        PARAMETER (N = 24, NZ = 136, IWLEN = 200)
23        INTEGER PE (N), DEGREE (N), NV (N), NEXT (N), PERM (N), W (N),
24     $      HEAD (N), PINV (N), LEN (N), AP (N+1), AI (NZ), IW (IWLEN)
25        CHARACTER A (24,24)
26
27        DATA AP
28     $      / 1, 9, 14, 19, 24, 29, 34, 42, 50, 53, 61, 66, 71,
29     $       76, 81, 86, 91, 94, 102, 110, 118, 123, 131, 134, 137 /
30        DATA AI /
31     $      6, 7, 13, 14, 18, 19, 20, 22,
32     $      9, 10, 14, 15, 18,
33     $      7, 12, 21, 22, 23,
34     $      8, 11, 16, 19, 20,
35     $      8, 10, 15, 16, 17,
36     $      1, 7, 13, 14, 18,
37     $      1, 3, 6, 12, 13, 20, 22, 24,
38     $      4, 5, 10, 15, 16, 17, 18, 19,
39     $      2, 10, 15,
40     $      2, 5, 8, 9, 14, 15, 18, 19,
41     $      4, 19, 20, 21, 22,
42     $      3, 7, 13, 22, 24,
43     $      1, 6, 7, 12, 24,
44     $      1, 2, 6, 10, 18,
45     $      2, 5, 8, 9, 10,
46     $      4, 5, 8, 17, 19,
47     $      5, 8, 16,
48     $      1, 2, 6, 8, 10, 14, 19, 20,
49     $      1, 4, 8, 10, 11, 16, 18, 20,
50     $      1, 4, 7, 11, 18, 19, 21, 22,
51     $      3, 11, 20, 22, 23,
52     $      1, 3, 7, 11, 12, 20, 21, 23,
53     $      3, 21, 22,
54     $      7, 12, 13 /
55
56C       print the input matrix
57        PRINT 11, N, N, NZ
5811      FORMAT ('AMD Fortran 77 demo, with the 24-by-24',
59     $      ' Harwell/Boeing matrix, can_24:'
60     $      /, 'Input matrix: ', I2, '-by-', I2,' with ',I3,' entries',
61     $      /, 'Note that the Fortran version of AMD requires that'
62     $      /, 'no diagonal entries be present.')
63        DO 20 J = 1, N
64            PRINT 21, J, AP (J+1) - AP (J), AP (J), AP (J+1)-1
6521          FORMAT ( /, 'Column: ', I2, ' number of entries: ', I2,
66     $          ' with row indices in AI (', I3, ' ... ', I3, ')')
67            PRINT 10, ((AI (P)), P = AP (J), AP (J+1) - 1)
6810          FORMAT ('    row indices: ', 24I3)
6920      CONTINUE
70
71C       print a character plot of the input matrix.  This is only
72C       reasonable because the matrix is small.
73        PRINT 31
7431      FORMAT ('Plot of input matrix pattern:')
75        DO 50 J = 1,N
76            DO 30 I = 1,N
77                A (I, J) = '.'
7830          CONTINUE
79C           add the diagonal entry to the plot
80            A (J, J) = 'X'
81            DO 40 P = AP (J), AP (J+1) - 1
82                I = AI (P)
83                A (I, J) = 'X'
8440          CONTINUE
8550      CONTINUE
86        PRINT 60, ((MOD (J, 10)), J = 1,N)
8760      FORMAT ('     ', 24I2)
88        DO 80 I = 1,N
89            PRINT 70, I, (A (I, J), J = 1,N)
9070          FORMAT (' ', I2, ': ', 24A2)
9180      CONTINUE
92
93        DO 190 METHOD = 1,2
94
95C           load the matrix into AMD's workspace
96            DO 90 J = 1,N
97                PE (J) = AP (J)
98                LEN (J) = AP (J+1) - AP (J)
9990          CONTINUE
100            DO 100 P = 1,NZ
101                IW (P) = AI (P)
102100         CONTINUE
103            PFREE = NZ + 1
104
105C           order the matrix using AMD or AMDBAR
106            IF (METHOD .EQ. 1) THEN
107                PRINT 101
108101             FORMAT (/, '------------------------------------------',
109     $                  /, 'ordering the matrix with AMD',
110     $                  /, '------------------------------------------')
111                CALL AMD (N, PE, IW, LEN, IWLEN, PFREE, NV, NEXT,
112     $              PERM, HEAD, PINV, DEGREE, NCMPA, W)
113            ELSE
114                PRINT 102
115102             FORMAT (/, '------------------------------------------',
116     $                  /, 'ordering the matrix with AMDBAR',
117     $                  /, '------------------------------------------')
118                CALL AMDBAR (N, PE, IW, LEN, IWLEN, PFREE, NV, NEXT,
119     $              PERM, HEAD, PINV, DEGREE, NCMPA, W)
120            ENDIF
121
122C           print the permutation vector, PERM, and its inverse, PINV.
123C           row/column J = PERM (K) is the Kth row/column in the
124C           permuted matrix.
125            PRINT 110, (PERM (K), K = 1,N)
126110         FORMAT (/, 'Permutation vector: ', /, 24I3)
127            PRINT 120, (PINV (J), J = 1,N)
128120         FORMAT (/, 'Inverse permutation vector: ', /, 24I3)
129
130C           print a character plot of the permuted matrix.
131            PRINT 121
132121         FORMAT ('Plot of permuted matrix pattern:')
133            DO 150 JNEW = 1,N
134                J = PERM (JNEW)
135                DO 130 INEW = 1,N
136                    A (INEW, JNEW) = '.'
137130             CONTINUE
138C               add the diagonal entry to the plot
139                A (JNEW, JNEW) = 'X'
140                DO 140 P = AP (J), AP (J+1) - 1
141                    INEW = PINV (AI (P))
142                    A (INEW, JNEW) = 'X'
143140             CONTINUE
144150         CONTINUE
145            PRINT 60, ((MOD (J, 10)), J = 1,N)
146            DO 160 I = 1,N
147                PRINT 70, I, (A (I, J), J = 1,N)
148160         CONTINUE
149
150C           print the permuted matrix, PERM*A*PERM'
151            DO 180 JNEW = 1,N
152                J = PERM (JNEW)
153                PRINT 171, JNEW, J, AP (J+1) - AP (J)
154171             FORMAT (/, 'New column: ', I2, ' old column: ', I2,
155     $              ' number of entries: ', I2)
156                PRINT 170, (PINV (AI (P)), P = AP (J), AP (J+1) - 1)
157170             FORMAT ('    new row indices: ', 24I3)
158180         CONTINUE
159190     CONTINUE
160        END
161