8303 IMPLICIT NONE
8304
8305 INTEGER, INTENT(IN) :: N, TOTEL, SIZE_SCHUR
8306 LOGICAL, INTENT(IN) :: AGG6
8307 INTEGER, INTENT(IN) :: THRESH
8308 INTEGER(8), INTENT(IN) :: IWLEN
8309 INTEGER, INTENT(IN) :: LISTVAR_SCHUR(max(1,SIZE_SCHUR))
8310
8311 INTEGER, INTENT(INOUT) :: LEN(N), IW(IWLEN)
8312
8313
8314 INTEGER, INTENT(OUT) :: NCMPA
8315 INTEGER, INTENT(OUT) :: ELEN(N), LAST(TOTEL), PARENT(N)
8316
8317
8318 INTEGER, INTENT(INOUT) :: NV(N)
8319 INTEGER(8), INTENT(INOUT) :: PFREE
8320 INTEGER(8), INTENT(INOUT) :: PE(N)
8321 INTEGER, INTENT(INOUT) :: PERM(N)
8322
8323
8324 INTEGER, INTENT(OUT) :: NDENSE(N), DEGREE(N),
8325 & HEAD(TOTEL), NEXT(N), W(N)
8326
8327
8328
8329
8330
8331
8332
8333
8334
8335
8336
8337
8338
8339
8340
8341
8342
8343
8344
8345
8346
8347
8348
8349
8350
8351
8352
8353
8354
8355
8356
8357
8358
8359
8360
8361
8362
8363
8364
8365
8366
8367
8368
8369
8370
8371
8372
8373
8374
8375
8376
8377
8378
8379
8380
8381
8382
8383
8384
8385
8386
8387
8388
8389
8390
8391
8392
8393
8394
8395
8396
8397
8398
8399
8400
8401
8402
8403
8404
8405
8406
8407
8408
8409
8410
8411
8412
8413
8414
8415
8416
8417
8418
8419
8420
8421
8422
8423
8424
8425
8426
8427
8428
8429
8430
8431
8432
8433
8434
8435
8436
8437
8438
8439
8440
8441
8442
8443
8444
8445
8446
8447
8448
8449
8450
8451
8452
8453
8454
8455
8456
8457
8458
8459
8460
8461
8462
8463
8464
8465 INTEGER THRESM, NDME, PERMeqN
8466 INTEGER NBD,NBED, NBDM, LASTD, NELME
8467 LOGICAL IDENSE
8468
8469
8470
8471
8472
8473
8474
8475
8476
8477
8478
8479
8480
8481
8482
8483
8484
8485
8486
8487
8488
8489
8490
8491
8492
8493
8494
8495
8496
8497
8498
8499
8500
8501
8502
8503
8504
8505
8506
8507
8508
8509
8510
8511
8512
8513
8514
8515
8516
8517
8518
8519
8520
8521
8522
8523
8524
8525
8526
8527
8528
8529
8530
8531
8532
8533
8534
8535
8536
8537
8538
8539
8540
8541
8542
8543
8544
8545
8546
8547
8548
8549
8550
8551
8552
8553
8554
8555
8556
8557
8558
8559
8560
8561
8562
8563
8564
8565
8566
8567
8568
8569
8570
8571
8572
8573
8574
8575
8576
8577
8578
8579
8580
8581
8582
8583
8584
8585
8586
8587
8588
8589
8590
8591
8592
8593
8594
8595
8596
8597
8598
8599
8600
8601
8602
8603
8604
8605
8606
8607
8608
8609
8610
8611
8612
8613
8614
8615
8616
8617
8618
8619
8620
8621
8622
8623
8624
8625
8626
8627
8628
8629
8630
8631
8632
8633
8634
8635
8636
8637
8638
8639
8640
8641
8642
8643
8644
8645
8646
8647
8648
8649
8650
8651
8652
8653
8654
8655
8656
8657
8658
8659
8660
8661
8662
8663
8664
8665
8666
8667
8668
8669
8670
8671
8672
8673
8674
8675
8676
8677
8678
8679
8680
8681
8682
8683
8684
8685
8686
8687
8688
8689
8690
8691
8692
8693
8694
8695
8696
8697
8698
8699
8700
8701
8702
8703
8704
8705
8706
8707
8708
8709
8710
8711
8712
8713
8714
8715
8716
8717
8718
8719
8720
8721
8722
8723
8724 INTEGER :: FDEG, ThresMin, ThresPrev, IBEGSchur, NbSchur,
8725 & ThresMinINIT
8726 INTEGER :: DEGMAX,THD, THDperm, THD_AGG
8727 DOUBLE PRECISION :: RELDEN
8728 LOGICAL :: AGG6_loc, DenseRows
8729 LOGICAL :: SchurON
8730 INTEGER :: DEG, DEGME, DEXT, DMAX, E, ELENME, ELN, I,
8731 & ILAST, INEXT, J, JLAST, JNEXT, K, KNT1, KNT2, KNT3,
8732 & LENJ, LN, ME, MINDEG, NEL,
8733 & NLEFT, NVI, NVJ, NVPIV, SLENME, WE, WFLG, WNVI, X
8734 INTEGER KNT1_UPDATED, KNT2_UPDATED
8735 INTEGER :: SIZE_SCHUR_LOC
8736 INTEGER(8) MAXMEM, MEM, NEWMEM
8737 INTEGER :: MAXINT_N
8738 INTEGER(8) :: HASH, HMOD
8739 LOGICAL :: COMPRESS
8740
8741
8742
8743
8744
8745
8746
8747
8748
8749
8750
8751
8752
8753
8754
8755
8756
8757
8758
8759
8760
8761
8762
8763
8764
8765
8766
8767
8768
8769
8770
8771
8772
8773
8774
8775
8776
8777
8778
8779
8780
8781
8782 INTEGER(8) P, P1, P2, P3, PDST, PEND, PJ, PME, PME1, PME2,
8783 & PN, PSRC, PLN, PELN
8784
8785
8786
8787
8788
8789
8790
8791
8792
8793
8794
8795
8796
8797
8798
8799
8800
8801
8802
8803
8804 INTRINSIC max,
min, mod, maxval
8805
8806
8807
8808 IF (n.EQ.1) THEN
8809 elen(1) = 1
8810 last(1) = 1
8811 pe(1) = 0_8
8812 IF (nv(1).LT.0) nv(1) = 1
8813 ncmpa = 0
8814 parent(1) = 0
8815 RETURN
8816 ENDIF
8817 agg6_loc = agg6
8818 denserows = .false.
8819
8820
8821
8822
8823
8824 size_schur_loc = size_schur
8825 size_schur_loc =
min(n,size_schur_loc)
8826 size_schur_loc =
max(0,size_schur_loc)
8827 schuron = (size_schur_loc > 0)
8828 ibegschur = n-size_schur_loc+1
8829 thresm = thresh
8830 IF (thresm.GT.n) thresm = n
8831 IF (thresm.LT.0) thresm = 0
8832
8833
8834 IF ( schuron ) THEN
8835 DO i= 1, n
8836 IF ( perm(i) .GE. ibegschur) THEN
8837 perm(i) = n + 1
8838
8839
8840 IF (len(i) .EQ.0) THEN
8841 pe(i) = 0_8
8842 ENDIF
8843 ENDIF
8844 ENDDO
8845 ENDIF
8846
8847 IF (schuron) THEN
8848
8849
8850
8851
8852
8853
8854
8855 thresm = n
8856 thresmin = n
8857 thresprev = n
8858 ELSE
8859 thresm =
max(int(31*n/32),thresm)
8860 thresm =
max(thresm,1)
8861
8862 degmax= maxval(len)
8863 relden=dble(pfree-1)/dble(n)
8864 thd = int(relden)*10 + (degmax-int(relden))/10 + 1
8865 IF (thd.LT.degmax) THEN
8866 denserows = .true.
8867 thdperm = n
8868 DO i = 1,n
8869 IF (len(i) .GT. thd) THEN
8870 thdperm =
min(thdperm,perm(i))
8871 ENDIF
8872 ENDDO
8873 thresm =
min(thresm, thdperm)
8874 ENDIF
8875
8876 thresmin =
max( 3*thresm / 4, 1)
8877 thresprev = thresm
8878
8879 ENDIF
8880
8881 thresmininit = thresmin/4
8882 thd_agg =
max(128,
min(totel/2048, 1024))
8883 IF (thresm.GT.0) THEN
8884 IF ((thresm.GT.n).OR.(thresm.LT.2)) THEN
8885
8886 thresm = n
8887 ENDIF
8888 ENDIF
8889 lastd = 0
8890 nbd = 0
8891 nbed = 0
8892 nbdm = 0
8893 wflg = 2
8894 maxint_n=huge(wflg)-totel
8895 mindeg = 1
8896 ncmpa = 0
8897 nel = 0
8898 hmod = int(
max(1, n-1),kind=8)
8899 dmax = 0
8900 mem = pfree - 1
8901 maxmem = mem
8902 DO i = 1, n
8903 ndense(i)= 0
8904 w(i) = 1
8905 elen(i) = 0
8906
8907
8908 ENDDO
8909 DO i=1, n
8910 last(i) = 0
8911 head(i) = 0
8912 ENDDO
8913
8914 IF(nv(1) .LT. 0) THEN
8915 compress = .false.
8916 ELSE
8917 compress = .true.
8918 ENDIF
8919 IF (compress) THEN
8920 DO i=1,n
8921 degree(i) = 0
8922 DO p= pe(i) , pe(i)+int(len(i)-1,8)
8923 degree(i) = degree(i) + nv(iw(p))
8924 ENDDO
8925 ENDDO
8926 ELSE
8927 DO i=1,n
8928 nv(i) = 1
8929 degree(i) = len(i)
8930 ENDDO
8931 ENDIF
8932
8933
8934
8935 DO 20 i = 1, n
8936 deg = degree(i)
8937 IF (perm(i).EQ.n) THEN
8938
8939 permeqn = i
8940 perm(i) = n-1
8941 ENDIF
8942 fdeg = perm(i)
8943 IF ( (deg .GT. 0).OR.(perm(i).EQ.n+1) ) THEN
8944
8945
8946
8947
8948
8949 IF ( (thresm.GT.0) .AND.
8950 & (fdeg .GT.thresm) ) THEN
8951
8952 nbd = nbd+nv(i)
8953 IF (fdeg.NE.n+1) THEN
8954
8955 degree(i) = degree(i)+totel+2
8956
8957 deg = n
8958 inext = head(deg)
8959 IF (inext .NE. 0) last(inext) = i
8960 next(i) = inext
8961 head(deg) = i
8962 last(i) = 0
8963 IF (lastd.EQ.0) lastd=i
8964 ELSE
8965
8966
8967
8968 nbed = nbed+nv(i)
8969 degree(i) = totel+1
8970
8971 deg = n
8972 IF (lastd.EQ.0) THEN
8973
8974 lastd = i
8975 head(deg) = i
8976 next(i) = 0
8977 last(i) = 0
8978 ELSE
8979 next(lastd) = i
8980 last(i) = lastd
8981 lastd = i
8982 next(i) = 0
8983 ENDIF
8984 ENDIF
8985 ELSE
8986
8987 inext = head(fdeg)
8988 IF (inext .NE. 0) last(inext) = i
8989 next(i) = inext
8990 head(fdeg) = i
8991 ENDIF
8992 ELSE
8993
8994
8995
8996
8997 nel = nel + nv(i)
8998 elen(i) = -nel
8999 pe (i) = 0_8
9000 w(i) = 0
9001 ENDIF
9002 20 CONTINUE
9003
9004
9005 IF ((nbd.EQ.0).AND.(thresm.GT.0)) thresm = n
9006
9007
9008
9009
9010 30 IF (nel .LT. totel) THEN
9011
9012
9013
9014
9015
9016
9017 DO 40 deg = mindeg, n
9018 me = head(deg)
9019 IF (me .GT. 0) GO TO 50
9020 40 CONTINUE
9021 50 mindeg = deg
9022
9023
9024
9025
9026
9027
9028
9029 IF ( (deg.NE.n) .AND.
9030 & (deg.GT.thresm+1) .AND. (nbd.GT.0) ) THEN
9031 mindeg = n
9032 GOTO 30
9033 ENDIF
9034 IF (degree(me).LE.totel) THEN
9035
9036
9037
9038 inext = next(me)
9039 IF (inext .NE. 0) last(inext) = 0
9040 head(deg) = inext
9041 ELSE
9042
9043
9044
9045
9046
9047 mindeg = 1
9048 nbdm =
max(nbdm,nbd)
9049 IF (degree(me).GT.totel+1) THEN
9050 IF (wflg .GT. maxint_n) THEN
9051 DO 52 x = 1, n
9052 IF (w(x) .NE. 0) w(x) = 1
9053 52 CONTINUE
9054 wflg = 2
9055 ENDIF
9056 wflg = wflg + 1
9057 51 CONTINUE
9058
9059
9060
9061 inext = next(me)
9062 IF (inext .NE. 0) THEN
9063 last(inext) = 0
9064 ELSE
9065 lastd = 0
9066 ENDIF
9067
9068
9069
9070
9071 ndense(me) = 0
9072 w(me) = wflg
9073 p1 = pe(me)
9074 p2 = p1 + int(len(me) -1,8)
9075
9076
9077
9078
9079
9080 pln = p1
9081 peln = p1
9082 DO 55 p=p1,p2
9083 e= iw(p)
9084 IF (w(e).EQ.wflg) GOTO 55
9085 w(e) = wflg
9086 IF (pe(e).LT.0_8) THEN
9087
9088 x = e
9089 53 x = int(-pe(x))
9090 IF (w(x) .EQ.wflg) GOTO 55
9091 w(x) = wflg
9092 IF ( pe(x) .LT. 0_8 ) GOTO 53
9093 e = x
9094 ENDIF
9095
9096
9097
9098
9099 IF (elen(e).LT.0) THEN
9100
9101 ndense(e) = ndense(e) - nv(me)
9102 iw(pln) = iw(peln)
9103 iw(peln) = e
9104 pln = pln+1_8
9105 peln = peln + 1_8
9106
9107
9108 pme1 = pe(e)
9109 DO 54 pme = pme1, pme1+int(len(e)-1,8)
9110 x = iw(pme)
9111 IF ((elen(x).GE.0).AND.(w(x).NE.wflg)) THEN
9112
9113 ndense(me) = ndense(me) + nv(x)
9114 w(x) = wflg
9115 ENDIF
9116 54 CONTINUE
9117 ELSE
9118
9119 ndense(me) = ndense(me) + nv(e)
9120 iw(pln)=e
9121 pln = pln+1_8
9122 ENDIF
9123 55 CONTINUE
9124
9125
9126
9127
9128
9129 wflg = wflg + 1
9130 len(me) = int(pln-p1)
9131 elen(me) = int(peln-p1)
9132 ndme = ndense(me)+nv(me)
9133 IF (ndense(me).EQ.0) ndense(me) =1
9134
9135
9136
9137 degree(me) = ndense(me)
9138 deg = perm(me)
9139 mindeg =
min(deg,mindeg)
9140 jnext = head(deg)
9141 IF (jnext.NE. 0) last(jnext) = me
9142 next(me) = jnext
9143 head(deg) = me
9144
9145
9146
9147 me = inext
9148 IF (me.NE.0) THEN
9149 IF (degree(me).GT.(totel+1) ) GOTO 51
9150 ENDIF
9151 head(n) = me
9152
9153
9154
9155 IF (thresm.LT.n) THEN
9156 thresmin =
max(thresm+thresmin,thresprev+thresmin/2+1)
9157 thresmin =
min(thresmin, n)
9158 thresprev = thresprev+(n-thresprev)/2+thresmininit
9160 & thresm + int(sqrt(dble(thresmin)))+ thresmininit ,
9161 & thresprev)
9162 thresm =
min(thresm,n)
9163 thresmin =
min(thresm, thresmin)
9164 thresprev = thresm
9165 ENDIF
9166 nbd = nbed
9167
9168
9169 GOTO 30
9170 ENDIF
9171
9172
9173 IF (degree(me).EQ.totel+1) THEN
9174
9175
9176 IF (nbd.NE.nbed) THEN
9177 write(6,*) ' ERROR in MUMPS_SYMQAMD quasi dense rows remains'
9179 ENDIF
9180 nbschur = 0
9181 nelme = -(nel+1)
9182 DO 59 x=1,n
9183 IF ((pe(x).GT.0) .AND. (elen(x).LT.0)) THEN
9184 pe(x) = int(-listvar_schur(1),8)
9185 ELSE IF ((pe(x).GT.0) .AND. (elen(x).LT.0)) THEN
9186
9187
9188 pe(x) = int(-listvar_schur(1),8)
9189
9190 ELSEIF (degree(x).EQ.totel+1) THEN
9191
9192 nel = nel + nv(x)
9193 pe(x) = int(-me,8)
9194 elen(x) = 0
9195 nv(x) = 0
9196 nbschur = nbschur+ 1
9197 ENDIF
9198 59 CONTINUE
9199 IF (nbschur.NE.size_schur_loc) then
9200 write(6,*) ' Internal error 2 in QAMD :',
9201 & ' Schur size expected:',size_schur_loc, 'Real:', nbschur
9203 ENDIF
9204
9205 elen(me) = nelme
9206 nv(me) = nbd
9207 pe(me) = 0_8
9208 IF (nel.NE.n) THEN
9209 write(6,*) 'Internal ERROR 2 detected in QAMD'
9210 write(6,*) ' NEL not equal to N: N, NEL =',n,nel
9212 ENDIF
9213 IF (me.NE. listvar_schur(1)) THEN
9214
9215 DO i=1, size_schur_loc
9216 pe(listvar_schur(i)) = int(-listvar_schur(1),8)
9217 ENDDO
9218 pe(listvar_schur(1)) = 0_8
9219 nv( listvar_schur(1))= nv(me)
9220 nv(me) = 0
9221 elen( listvar_schur(1)) = elen(me)
9222 elen(me) = 0
9223 ENDIF
9224 GOTO 265
9225 ENDIF
9226 ENDIF
9227
9228
9229
9230
9231
9232
9233 elenme = elen(me)
9234 elen(me) = - (nel + 1)
9235 nvpiv = nv(me)
9236 nel = nel + nvpiv
9237 ndense(me) = 0
9238
9239
9240
9241
9242
9243
9244
9245
9246
9247
9248
9249 nv(me) = -nvpiv
9250 degme = 0
9251 IF (elenme .EQ. 0) THEN
9252
9253
9254
9255 pme1 = pe(me)
9256 pme2 = pme1 - 1
9257 DO 60 p = pme1, pme1 + int(len(me) - 1,8)
9258 i = iw(p)
9259 nvi = nv(i)
9260 IF (nvi .GT. 0) THEN
9261
9262
9263
9264
9265 degme = degme + nvi
9266
9267 nv(i) = -nvi
9268 pme2 = pme2 + 1
9269 iw(pme2) = i
9270
9271
9272
9273
9274 IF (degree(i).LE.totel) THEN
9275 ilast = last(i)
9276 inext = next(i)
9277 IF (inext .NE. 0) last(inext) = ilast
9278 IF (ilast .NE. 0) THEN
9279 next(ilast) = inext
9280 ELSE
9281
9282 head(perm(i)) = inext
9283 ENDIF
9284 ELSE
9285 ndense(me) = ndense(me) + nvi
9286 ENDIF
9287 ENDIF
9288 60 CONTINUE
9289
9290 newmem = 0
9291 ELSE
9292
9293
9294
9295 p = pe(me)
9296 pme1 = pfree
9297 slenme = len(me) - elenme
9298 knt1_updated = 0
9299 DO 120 knt1 = 1, elenme + 1
9300 knt1_updated = knt1_updated +1
9301 IF (knt1 .GT. elenme) THEN
9302
9303 e = me
9304 pj = p
9305 ln = slenme
9306 ELSE
9307
9308 e = iw(p)
9309 p = p + 1
9310 pj = pe(e)
9311 ln = len(e)
9312 ENDIF
9313
9314
9315
9316
9317
9318
9319 knt2_updated = 0
9320 DO 110 knt2 = 1, ln
9321 knt2_updated = knt2_updated+1
9322 i = iw(pj)
9323 pj = pj + 1
9324 nvi = nv(i)
9325 IF (nvi .GT. 0) THEN
9326
9327
9328
9329 IF (pfree .GT. iwlen) THEN
9330
9331
9332
9333
9334 pe(me) = p
9335 len(me) = len(me) - knt1_updated
9336
9337
9338 knt1_updated = 0
9339
9340 IF (len(me) .EQ. 0) pe(me) = 0
9341 pe(e) = pj
9342 len(e) = ln - knt2_updated
9343
9344
9345 knt2_updated = 0
9346
9347 IF (len(e) .EQ. 0) pe(e) = 0
9348 ncmpa = ncmpa + 1
9349
9350
9351 DO 70 j = 1, n
9352 pn = pe(j)
9353 IF (pn .GT. 0) THEN
9354 pe(j) = int(iw(pn),8)
9355 iw(pn) = -j
9356 ENDIF
9357 70 CONTINUE
9358
9359 pdst = 1
9360 psrc = 1
9361 pend = pme1 - 1
9362
9363 80 CONTINUE
9364 IF (psrc .LE. pend) THEN
9365
9366 j = -iw(psrc)
9367 psrc = psrc + 1
9368 IF (j .GT. 0) THEN
9369 iw(pdst) = int(pe(j))
9370 pe(j) = pdst
9371 pdst = pdst + 1
9372
9373 lenj = len(j)
9374 DO 90 knt3 = 0, lenj - 2
9375 iw(pdst + knt3) = iw(psrc + knt3)
9376 90 CONTINUE
9377 pdst = pdst + lenj - 1
9378 psrc = psrc + lenj - 1
9379 ENDIF
9380 GO TO 80
9381 ENDIF
9382
9383 p1 = pdst
9384 DO 100 psrc = pme1, pfree - 1
9385 iw(pdst) = iw(psrc)
9386 pdst = pdst + 1
9387 100 CONTINUE
9388 pme1 = p1
9389 pfree = pdst
9390 pj = pe(e)
9391 p = pe(me)
9392 ENDIF
9393
9394
9395
9396
9397 degme = degme + nvi
9398
9399 nv(i) = -nvi
9400 iw(pfree) = i
9401 pfree = pfree + 1
9402
9403
9404
9405
9406 IF (degree(i).LE.totel) THEN
9407 ilast = last(i)
9408 inext = next(i)
9409 IF (inext .NE. 0) last(inext) = ilast
9410 IF (ilast .NE. 0) THEN
9411 next(ilast) = inext
9412 ELSE
9413
9414 head(perm(i)) = inext
9415 ENDIF
9416 ELSE
9417 ndense(me) = ndense(me) + nvi
9418 ENDIF
9419 ENDIF
9420 110 CONTINUE
9421 IF (e .NE. me) THEN
9422
9423
9424 pe(e) = int(-me,8)
9425 w(e) = 0
9426 ENDIF
9427 120 CONTINUE
9428 pme2 = pfree - 1
9429
9430 newmem = pfree - pme1
9431 mem = mem + newmem
9432 maxmem =
max(maxmem, mem)
9433 ENDIF
9434
9435
9436
9437
9438 degree(me) = degme
9439 pe(me) = pme1
9440 len(me) = int(pme2 - pme1 + 1_8)
9441
9442
9443
9444
9445 IF (wflg .GT. maxint_n) THEN
9446 DO 130 x = 1, n
9447 IF (w(x) .NE. 0) w(x) = 1
9448 130 CONTINUE
9449 wflg = 2
9450 ENDIF
9451
9452
9453
9454
9455
9456
9457
9458
9459
9460
9461
9462
9463
9464
9465
9466
9467
9468
9469
9470
9471
9472 DO 150 pme = pme1, pme2
9473 i = iw(pme)
9474 IF (degree(i).GT.totel) GOTO 150
9475 eln = elen(i)
9476 IF (eln .GT. 0) THEN
9477
9478 nvi = -nv(i)
9479 wnvi = wflg - nvi
9480 DO 140 p = pe(i), pe(i) + int(eln - 1,8)
9481 e = iw(p)
9482 we = w(e)
9483 IF (we .GE. wflg) THEN
9484
9485 we = we - nvi
9486 ELSE IF (we .NE. 0) THEN
9487
9488
9489 we = degree(e) + wnvi - ndense(e)
9490
9491 ENDIF
9492 w(e) = we
9493 140 CONTINUE
9494 ENDIF
9495 150 CONTINUE
9496
9497
9498
9499
9500
9501
9502
9503
9504
9505 agg6_loc = (agg6 .OR. (degree(me) .LT. thd_agg))
9506 DO 180 pme = pme1, pme2
9507 i = iw(pme)
9508 IF (degree(i).GT.totel) GOTO 180
9509 p1 = pe(i)
9510 p2 = p1 + int(elen(i) - 1,8)
9511 pn = p1
9512 hash = 0_8
9513 deg = 0
9514
9515
9516
9517 DO 160 p = p1, p2
9518 e = iw(p)
9519
9520 dext = w(e) - wflg
9521 IF (dext .GT. 0) THEN
9522 deg = deg + dext
9523 iw(pn) = e
9524 pn = pn + 1_8
9525 hash = hash + int(e,kind=8)
9526
9527
9528
9529 ELSE IF (.NOT. agg6_loc .AND. dext .EQ. 0) THEN
9530 iw(pn) = e
9531 pn = pn + 1_8
9532 hash = hash + int(e,kind=8)
9533
9534
9535
9536
9537 ELSE IF (agg6_loc .AND. (dext .EQ. 0) .AND.
9538 & ((ndense(me).EQ.nbd).OR.(ndense(e).EQ.0))) THEN
9539
9540
9541
9542 pe(e) = int(-me,8)
9543 w(e) = 0
9544 ELSE IF (agg6_loc .AND. dext.EQ.0) THEN
9545 iw(pn) = e
9546 pn = pn+1
9547 hash = hash + int(e,kind=8)
9548 ENDIF
9549 160 CONTINUE
9550
9551 elen(i) = int(pn - p1 + 1)
9552
9553
9554
9555 p3 = pn
9556 DO 170 p = p2 + 1, p1 + int(len(i) - 1,8)
9557 j = iw(p)
9558 nvj = nv(j)
9559 IF (nvj .GT. 0) THEN
9560
9561
9562
9563 IF (degree(j).LE.totel) deg=deg+nvj
9564 iw(pn) = j
9565 pn = pn + 1
9566 hash = hash + int(j,kind=8)
9567 ENDIF
9568 170 CONTINUE
9569
9570
9571
9572 IF (((elen(i).EQ.1).AND.(p3.EQ.pn))
9573 & .OR.
9574 & (agg6_loc.AND.(deg .EQ. 0).AND.(ndense(me).EQ.nbd))
9575 & )
9576 & THEN
9577
9578
9579
9580
9581
9582
9583
9584 pe(i) = int(-me,8)
9585 nvi = -nv(i)
9586 degme = degme - nvi
9587 nvpiv = nvpiv + nvi
9588 nel = nel + nvi
9589 nv(i) = 0
9590 elen(i) = 0
9591 ELSE
9592
9593
9594
9595
9596
9597 degree(i) =
min(deg+nbd-ndense(me),
9598 & degree(i))
9599
9600
9601
9602
9603 iw(pn) = iw(p3)
9604
9605 iw(p3) = iw(p1)
9606
9607 iw(p1) = me
9608
9609 len(i) = int(pn - p1 + 1)
9610
9611
9612
9613 hash = mod(hash, hmod) + 1_8
9614 j = head(hash)
9615 IF (j .LE. 0) THEN
9616
9617 next(i) = -j
9618 head(hash) = -i
9619 ELSE
9620
9621
9622 next(i) = last(j)
9623 last(j) = i
9624 ENDIF
9625 last(i) = int(hash,kind=kind(last))
9626 ENDIF
9627 180 CONTINUE
9628 degree(me) = degme
9629
9630
9631
9632 dmax =
max(dmax, degme)
9633 wflg = wflg + dmax
9634
9635 IF (wflg .GT. maxint_n) THEN
9636 DO 190 x = 1, n
9637 IF (w(x) .NE. 0) w(x) = 1
9638 190 CONTINUE
9639 wflg = 2
9640 ENDIF
9641
9642
9643
9644
9645 DO 250 pme = pme1, pme2
9646 i = iw(pme)
9647 IF ( (nv(i).LT.0) .AND. (degree(i).LE.totel) ) THEN
9648
9649
9650
9651
9652
9653
9654
9655 hash = int(last(i),kind=8)
9656
9657 j = head(hash)
9658 IF (j .EQ. 0) GO TO 250
9659 IF (j .LT. 0) THEN
9660
9661 i = -j
9662 head(hash) = 0
9663 ELSE
9664
9665 i = last(j)
9666 last(j) = 0
9667 ENDIF
9668 IF (i .EQ. 0) GO TO 250
9669
9670 200 CONTINUE
9671 IF (next(i) .NE. 0) THEN
9672 x = i
9673
9674
9675
9676
9677
9678 ln = len(i)
9679 eln = elen(i)
9680
9681 DO 210 p = pe(i) + 1, pe(i) + int(ln - 1,8)
9682 w(iw(p)) = wflg
9683 210 CONTINUE
9684
9685
9686
9687 jlast = i
9688 j = next(i)
9689
9690 220 CONTINUE
9691 IF (j .NE. 0) THEN
9692
9693
9694
9695
9696 IF (len(j) .NE. ln) GO TO 240
9697
9698 IF (elen(j) .NE. eln) GO TO 240
9699
9700 DO 230 p = pe(j) + 1, pe(j) + int(ln - 1,8)
9701
9702 IF (w(iw(p)) .NE. wflg) GO TO 240
9703 230 CONTINUE
9704
9705
9706
9707 IF (perm(j).GT.perm(x)) THEN
9708
9709 pe(j) = int(-x,8)
9710 nv(x) = nv(x) + nv(j)
9711 nv(j) = 0
9712 elen(j) = 0
9713 ELSE
9714
9715 pe(x) = int(-j,8)
9716 nv (j) = nv(x) + nv(j)
9717 nv(x) = 0
9718 elen(x) = 0
9719 x = j
9720 ENDIF
9721
9722
9723
9724
9725 j = next(j)
9726 next(jlast) = j
9727 GO TO 220
9728
9729 240 CONTINUE
9730
9731
9732 jlast = j
9733 j = next(j)
9734 GO TO 220
9735 ENDIF
9736
9737
9738
9739
9740 wflg = wflg + 1
9741 i = next(i)
9742 IF (i .NE. 0) GO TO 200
9743 ENDIF
9744 ENDIF
9745 250 CONTINUE
9746
9747
9748
9749
9750
9751
9752
9753 IF ( .NOT.denserows.AND.(thresm .GT. 0).AND.(thresm.LT.n) )
9754 & THEN
9755 thresm =
max(thresmin, thresm-nvpiv)
9756 ENDIF
9757 p = pme1
9758 nleft = totel - nel
9759 DO 260 pme = pme1, pme2
9760 i = iw(pme)
9761 nvi = -nv(i)
9762 IF (nvi .GT. 0) THEN
9763
9764
9765 nv(i) = nvi
9766 IF (degree(i).LE.totel) THEN
9767
9768
9769
9770 deg =
min(degree(i)+ degme - nvi, nleft - nvi)
9771 degree(i) = deg
9772 idense = .false.
9773
9774
9775
9776
9777 IF (thresm.GT.0) THEN
9778 IF (perm(i) .GT. thresm) THEN
9779
9780 idense = .true.
9781
9782 degree(i) = degree(i)+totel+2
9783 ENDIF
9784 IF (idense) THEN
9785
9786
9787 p1 = pe(i)
9788 p2 = p1 + int(elen(i) - 1,8)
9789 IF (p2.GE.p1) THEN
9790 DO 264 pj=p1,p2
9791 e= iw(pj)
9792 ndense(e) = ndense(e) + nvi
9793 264 CONTINUE
9794 ENDIF
9795
9796 nbd = nbd+nvi
9797 fdeg = n
9798 deg = n
9799
9800 inext = head(deg)
9801 IF (inext .NE. 0) last(inext) = i
9802 next(i) = inext
9803 head(deg) = i
9804 last(i) = 0
9805 IF (lastd.EQ.0) lastd=i
9806
9807 ENDIF
9808
9809 ENDIF
9810
9811 IF (.NOT.idense) THEN
9812 fdeg = perm(i)
9813
9814
9815
9816 inext = head(fdeg)
9817 IF (inext .NE. 0) last(inext) = i
9818 next(i) = inext
9819 last(i) = 0
9820 head(fdeg) = i
9821 ENDIF
9822
9823
9824
9825 mindeg =
min(mindeg, fdeg)
9826 ENDIF
9827
9828
9829
9830 iw(p) = i
9831 p = p + 1
9832 ENDIF
9833 260 CONTINUE
9834
9835
9836
9837 nv(me) = nvpiv + degme
9838
9839
9840 len(me) = int(p - pme1)
9841 IF (len(me) .EQ. 0) THEN
9842
9843 pe(me) = 0_8
9844 w(me) = 0
9845 ENDIF
9846 IF (newmem .NE. 0) THEN
9847
9848
9849
9850 pfree = p
9851 mem = mem - newmem + int(len(me),8)
9852 ENDIF
9853
9854
9855 GO TO 30
9856 ENDIF
9857
9858 265 CONTINUE
9859
9860
9861
9862
9863
9864
9865
9866
9867
9868
9869
9870
9871
9872 DO 290 i = 1, n
9873 IF (elen(i) .EQ. 0) THEN
9874
9875
9876
9877
9878
9879
9880 j = int(-pe(i))
9881
9882 270 CONTINUE
9883 IF (elen(j) .GE. 0) THEN
9884 j = int(-pe(j))
9885 GO TO 270
9886 ENDIF
9887 e = j
9888
9889
9890
9891 k = -elen(e)
9892
9893
9894
9895
9896
9897
9898 j = i
9899
9900 280 CONTINUE
9901 IF (elen(j) .GE. 0) THEN
9902 jnext = int(-pe(j))
9903 pe(j) = int(-e,8)
9904 IF (elen(j) .EQ. 0) THEN
9905
9906 elen(j) = k
9907 k = k + 1
9908 ENDIF
9909 j = jnext
9910 GO TO 280
9911 ENDIF
9912
9913 elen(e) = -k
9914 ENDIF
9915 290 CONTINUE
9916
9917
9918
9919
9920 DO 300 i = 1, n
9921 k = abs(elen(i))
9922
9923
9924 elen(i) = k
9925 300 CONTINUE
9926 IF (.NOT.schuron) THEN
9927
9928
9929
9930 perm(permeqn) = n
9931 ENDIF
9932
9933
9934
9935
9936
9937
9938
9939
9940 pfree = maxmem
9941
9942
9943 DO i=1,n
9944 parent(i) = int(pe(i))
9945 ENDDO
9946
9947 RETURN