        SUBROUTINE  MD
     *     (N, IA,JA, MAX, V,L, HEAD,LAST,NEXT, MARK, FLAG)               OD 175
C                                                                         OD 176
C  DESCRIPTION                                                            OD 177
C                                                                         OD 178
C    MD FINDS A MINIMUM DEGREE ORDERING OF THE ROWS AND COLUMNS OF A      OD 179
C    SYMMETRIC MATRIX M STORED IN (IA,JA,A) FORMAT.                       OD 180
C                                                                         OD 181
C                                                                         OD 182
C  ADDITIONAL PARAMETERS                                                  OD 183
C                                                                         OD 184
C    MAX  - DECLARED DIMENSION OF THE ONE-DIMENSIONAL ARRAYS V AND L;     OD 185
C           MAX MUST BE AT LEAST  N+2K,  WHERE K IS THE NUMBER OF         OD 186
C           NONZEROES IN THE STRICT UPPER TRIANGLE OF M                   OD 187
C                                                                         OD 188
C    V    - INTEGER ONE-DIMENSIONAL WORK ARRAY;  DIMENSION = MAX          OD 189
C                                                                         OD 190
C    L    - INTEGER ONE-DIMENSIONAL WORK ARRAY;  DIMENSION = MAX          OD 191
C                                                                         OD 192
C    HEAD - INTEGER ONE-DIMENSIONAL WORK ARRAY;  DIMENSION = N            OD 193
C                                                                         OD 194
C    LAST - INTEGER ONE-DIMENSIONAL ARRAY USED TO RETURN THE PERMUTATION  OD 195
C           OF THE ROWS AND COLUMNS OF M CORRESPONDING TO THE MINIMUM     OD 196
C           DEGREE ORDERING;  DIMENSION = N                               OD 197
C                                                                         OD 198
C    NEXT - INTEGER ONE-DIMENSIONAL ARRAY USED TO RETURN THE INVERSE OF   OD 199
C           THE PERMUTATION RETURNED IN LAST;  DIMENSION = N              OD 200
C                                                                         OD 201
C    MARK - INTEGER ONE-DIMENSIONAL WORK ARRAY (MAY BE THE SAME AS V);    OD 202
C           DIMENSION = N                                                 OD 203
C                                                                         OD 204
C    FLAG - INTEGER ERROR FLAG;  VALUES AND THEIR MEANINGS ARE -          OD 205
C             0      NO ERRORS DETECTED                                   OD 206
C             11N+1  INSUFFICIENT STORAGE IN MD                           OD 207
C                                                                         OD 208
C                                                                         OD 209
C  DEFINITIONS OF INTERNAL PARAMETERS                                     OD 210
C                                                                         OD 211
C    ---------+---------------------------------------------------------  OD 212
C    V(S)     \ VALUE FIELD OF LIST ENTRY                                 OD 213
C    ---------+---------------------------------------------------------  OD 214
C    L(S)     \ LINK FIELD OF LIST ENTRY  (0 => END OF LIST)              OD 215
C    ---------+---------------------------------------------------------  OD 216
C    L(VI)    \ POINTER TO ELEMENT LIST OF UNELIMINATED VERTEX VI         OD 217
C    ---------+---------------------------------------------------------  OD 218
C    L(EJ)    \ POINTER TO BOUNDARY LIST OF ACTIVE ELEMENT EJ             OD 219
C    ---------+---------------------------------------------------------  OD 220
C    HEAD(D)  \ VJ => VJ HEAD OF D-LIST D                                 OD 221
C             \  0 => NO VERTEX IN D-LIST D                               OD 222
C                                                                         OD 223
C                                                                         OD 224
C             \                  VI UNELIMINATED VERTEX                   OD 225
C             \          VI IN EK           \       VI NOT IN EK          OD 226
C    ---------+-----------------------------+---------------------------  OD 227
C    NEXT(VI) \ UNDEFINED BUT NONNEGATIVE   \ VJ => VJ NEXT IN D-LIST     OD 228
C             \                             \  0 => VI TAIL OF D-LIST     OD 229
C    ---------+-----------------------------+---------------------------  OD 230
C    LAST(VI) \ (NOT SET UNTIL MDP)         \ -D => VI HEAD OF D-LIST D   OD 231
C             \-VK => COMPUTE DEGREE        \ VJ => VJ LAST IN D-LIST     OD 232
C             \ EJ => VI PROTOTYPE OF EJ    \  0 => VI NOT IN ANY D-LIST  OD 233
C             \  0 => DO NOT COMPUTE DEGREE \                             OD 234
C    ---------+-----------------------------+---------------------------  OD 235
C    MARK(VI) \ MARK(VK)                    \ NONNEGATIVE TAG < MARK(VK)  OD 236
C                                                                         OD 237
C                                                                         OD 238
C             \                   VI ELIMINATED VERTEX                    OD 239
C             \      EI ACTIVE ELEMENT      \           OTHERWISE         OD 240
C    ---------+-----------------------------+---------------------------  OD 241
C    NEXT(VI) \ -J => VI WAS J-TH VERTEX    \ -J => VI WAS J-TH VERTEX    OD 242
C             \       TO BE ELIMINATED      \       TO BE ELIMINATED      OD 243
C    ---------+-----------------------------+---------------------------  OD 244
C    LAST(VI) \  M => SIZE OF EI = M        \ UNDEFINED                   OD 245
C    ---------+-----------------------------+---------------------------  OD 246
C    MARK(VI) \ -M => OVERLAP COUNT OF EI   \ UNDEFINED                   OD 247
C             \       WITH EK = M           \                             OD 248
C             \ OTHERWISE NONNEGATIVE TAG   \                             OD 249
C             \       < MARK(VK)            \                             OD 250
C                                                                         OD 251
C-----------------------------------------------------------------------  OD 252
C                                                                         OD 253
        INTEGER  IA(1), JA(1),  V(1), L(1),  HEAD(1), LAST(1), NEXT(1),   OD 254
     *     MARK(1),  FLAG,  TAG, DMIN, VK,EK, TAIL                        OD 255
        EQUIVALENCE  (VK,EK)                                              OD 256
C                                                                         OD 257
C----INITIALIZATION                                                       OD 258
        TAG = 0                                                           OD 259
        CALL  MDI                                                         OD 260
     *     (N, IA,JA, MAX,V,L, HEAD,LAST,NEXT, MARK,TAG, FLAG)            OD 261
        IF (FLAG.NE.0)  RETURN                                            OD 262
C                                                                         OD 263
        K = 0                                                             OD 264
        DMIN = 1                                                          OD 265
C                                                                         OD 266
C----WHILE  K < N  DO                                                     OD 267
   1    IF (K.GE.N)  GO TO 4                                              OD 268
C                                                                         OD 269
C------SEARCH FOR VERTEX OF MINIMUM DEGREE                                OD 270
   2      IF (HEAD(DMIN).GT.0)  GO TO 3                                   OD 271
            DMIN = DMIN + 1                                               OD 272
            GO TO 2                                                       OD 273
C                                                                         OD 274
C------REMOVE VERTEX VK OF MINIMUM DEGREE FROM DEGREE LIST                OD 275
   3      VK = HEAD(DMIN)                                                 OD 276
          HEAD(DMIN) = NEXT(VK)                                           OD 277
          IF (HEAD(DMIN).GT.0)  LAST(HEAD(DMIN)) = -DMIN                  OD 278
C                                                                         OD 279
C------NUMBER VERTEX VK, ADJUST TAG, AND TAG VK                           OD 280
          K = K+1                                                         OD 281
          NEXT(VK) = -K                                                   OD 282
          LAST(EK) = DMIN - 1                                             OD 283
          TAG = TAG + LAST(EK)                                            OD 284
          MARK(VK) = TAG                                                  OD 285
C                                                                         OD 286
C------FORM ELEMENT EK FROM UNELIMINATED NEIGHBORS OF VK                  OD 287
          CALL  MDM                                                       OD 288
     *       (VK,TAIL, V,L, LAST,NEXT, MARK)                              OD 289
C                                                                         OD 290
C------PURGE INACTIVE ELEMENTS AND DO MASS ELIMINATION                    OD 291
          CALL  MDP                                                       OD 292
     *       (K,EK,TAIL, V,L, HEAD,LAST,NEXT, MARK)                       OD 293
C                                                                         OD 294
C------UPDATE DEGREES OF UNELIMINATED VERTICES IN EK                      OD 295
          CALL  MDU                                                       OD 296
     *       (EK,DMIN, V,L, HEAD,LAST,NEXT, MARK)                         OD 297
C                                                                         OD 298
          GO TO 1                                                         OD 299
C                                                                         OD 300
C----GENERATE INVERSE PERMUTATION FROM PERMUTATION                        OD 301
   4    DO 5 K=1,N                                                        OD 302
          NEXT(K) = -NEXT(K)                                              OD 303
   5      LAST(NEXT(K)) = K                                               OD 304
C                                                                         OD 305
        RETURN                                                            OD 306
        END                                                               OD 307
