SUBROUTINE DSM(M,N,NPAIRS,INDROW,INDCOL,NGRP,MAXGRP,MINGRP, * INFO,IPNTR,JPNTR,IWA,LIWA,BWA) INTEGER M,N,NPAIRS,MAXGRP,MINGRP,INFO,LIWA INTEGER INDROW(NPAIRS),INDCOL(NPAIRS),NGRP(N), * IPNTR(1),JPNTR(1),IWA(LIWA) LOGICAL BWA(N) C ********** C C SUBROUTINE DSM C C THE PURPOSE OF DSM IS TO DETERMINE AN OPTIMAL OR NEAR- C OPTIMAL CONSISTENT PARTITION OF THE COLUMNS OF A SPARSE C M BY N MATRIX A. C C THE SPARSITY PATTERN OF THE MATRIX A IS SPECIFIED BY C THE ARRAYS INDROW AND INDCOL. ON INPUT THE INDICES C FOR THE NON-ZERO ELEMENTS OF A ARE C C INDROW(K),INDCOL(K), K = 1,2,...,NPAIRS. C C THE (INDROW,INDCOL) PAIRS MAY BE SPECIFIED IN ANY ORDER. C DUPLICATE INPUT PAIRS ARE PERMITTED, BUT THE SUBROUTINE C ELIMINATES THEM. C C THE SUBROUTINE PARTITIONS THE COLUMNS OF A INTO GROUPS C SUCH THAT COLUMNS IN THE SAME GROUP DO NOT HAVE A C NON-ZERO IN THE SAME ROW POSITION. A PARTITION OF THE C COLUMNS OF A WITH THIS PROPERTY IS CONSISTENT WITH THE C DIRECT DETERMINATION OF A. C C THE SUBROUTINE STATEMENT IS C C SUBROUTINE DSM(M,N,NPAIRS,INDROW,INDCOL,NGRP,MAXGRP,MINGRP, C INFO,IPNTR,JPNTR,IWA,LIWA,BWA) C C WHERE C C M IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER C OF ROWS OF A. C C N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER C OF COLUMNS OF A. C C NPAIRS IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE C NUMBER OF (INDROW,INDCOL) PAIRS USED TO DESCRIBE THE C SPARSITY PATTERN OF A. C C INDROW IS AN INTEGER ARRAY OF LENGTH NPAIRS. ON INPUT INDROW C MUST CONTAIN THE ROW INDICES OF THE NON-ZERO ELEMENTS OF A. C ON OUTPUT INDROW IS PERMUTED SO THAT THE CORRESPONDING C COLUMN INDICES ARE IN NON-DECREASING ORDER. THE COLUMN C INDICES CAN BE RECOVERED FROM THE ARRAY JPNTR. C C INDCOL IS AN INTEGER ARRAY OF LENGTH NPAIRS. ON INPUT INDCOL C MUST CONTAIN THE COLUMN INDICES OF THE NON-ZERO ELEMENTS OF C A. ON OUTPUT INDCOL IS PERMUTED SO THAT THE CORRESPONDING C ROW INDICES ARE IN NON-DECREASING ORDER. THE ROW INDICES C CAN BE RECOVERED FROM THE ARRAY IPNTR. C C NGRP IS AN INTEGER OUTPUT ARRAY OF LENGTH N WHICH SPECIFIES C THE PARTITION OF THE COLUMNS OF A. COLUMN JCOL BELONGS C TO GROUP NGRP(JCOL). C C MAXGRP IS AN INTEGER OUTPUT VARIABLE WHICH SPECIFIES THE C NUMBER OF GROUPS IN THE PARTITION OF THE COLUMNS OF A. C C MINGRP IS AN INTEGER OUTPUT VARIABLE WHICH SPECIFIES A LOWER C BOUND FOR THE NUMBER OF GROUPS IN ANY CONSISTENT PARTITION C OF THE COLUMNS OF A. C C INFO IS AN INTEGER OUTPUT VARIABLE SET AS FOLLOWS. FOR C NORMAL TERMINATION INFO = 1. IF M, N, OR NPAIRS IS NOT C POSITIVE OR LIWA IS LESS THAN MAX(M,6*N), THEN INFO = 0. C IF THE K-TH ELEMENT OF INDROW IS NOT AN INTEGER BETWEEN C 1 AND M OR THE K-TH ELEMENT OF INDCOL IS NOT AN INTEGER C BETWEEN 1 AND N, THEN INFO = -K. C C IPNTR IS AN INTEGER OUTPUT ARRAY OF LENGTH M + 1 WHICH C SPECIFIES THE LOCATIONS OF THE COLUMN INDICES IN INDCOL. C THE COLUMN INDICES FOR ROW I ARE C C INDCOL(K), K = IPNTR(I),...,IPNTR(I+1)-1. C C NOTE THAT IPNTR(M+1)-1 IS THEN THE NUMBER OF NON-ZERO C ELEMENTS OF THE MATRIX A. C C JPNTR IS AN INTEGER OUTPUT ARRAY OF LENGTH N + 1 WHICH C SPECIFIES THE LOCATIONS OF THE ROW INDICES IN INDROW. C THE ROW INDICES FOR COLUMN J ARE C C INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. C C NOTE THAT JPNTR(N+1)-1 IS THEN THE NUMBER OF NON-ZERO C ELEMENTS OF THE MATRIX A. C C IWA IS AN INTEGER WORK ARRAY OF LENGTH LIWA. C C LIWA IS A POSITIVE INTEGER INPUT VARIABLE NOT LESS THAN C MAX(M,6*N). C C BWA IS A LOGICAL WORK ARRAY OF LENGTH N. C C SUBPROGRAMS CALLED C C MINPACK-SUPPLIED ...D7EGR,I7DO,N7MSRT,M7SEQ,S7ETR,M7SLO,S7RTDT C C FORTRAN-SUPPLIED ... MAX0 C C ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. C THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE C C ********** INTEGER I,IR,J,JP,JPL,JPU,K,MAXCLQ,NNZ,NUMGRP C C CHECK THE INPUT DATA. C INFO = 0 IF (M .LT. 1 .OR. N .LT. 1 .OR. NPAIRS .LT. 1 .OR. * LIWA .LT. MAX0(M,6*N)) GO TO 130 DO 10 K = 1, NPAIRS INFO = -K IF (INDROW(K) .LT. 1 .OR. INDROW(K) .GT. M .OR. * INDCOL(K) .LT. 1 .OR. INDCOL(K) .GT. N) GO TO 130 10 CONTINUE INFO = 1 C C SORT THE DATA STRUCTURE BY COLUMNS. C CALL S7RTDT(N,NPAIRS,INDROW,INDCOL,JPNTR,IWA(1)) C C COMPRESS THE DATA AND DETERMINE THE NUMBER OF C NON-ZERO ELEMENTS OF A. C DO 20 I = 1, M IWA(I) = 0 20 CONTINUE NNZ = 0 DO 70 J = 1, N JPL = JPNTR(J) JPU = JPNTR(J+1) - 1 JPNTR(J) = NNZ + 1 IF (JPU .LT. JPL) GO TO 60 DO 40 JP = JPL, JPU IR = INDROW(JP) IF (IWA(IR) .NE. 0) GO TO 30 NNZ = NNZ + 1 INDROW(NNZ) = IR IWA(IR) = 1 30 CONTINUE 40 CONTINUE JPL = JPNTR(J) DO 50 JP = JPL, NNZ IR = INDROW(JP) IWA(IR) = 0 50 CONTINUE 60 CONTINUE 70 CONTINUE JPNTR(N+1) = NNZ + 1 C C EXTEND THE DATA STRUCTURE TO ROWS. C CALL S7ETR(M,N,INDROW,JPNTR,INDCOL,IPNTR,IWA(1)) C C DETERMINE A LOWER BOUND FOR THE NUMBER OF GROUPS. C MINGRP = 0 DO 80 I = 1, M MINGRP = MAX0(MINGRP,IPNTR(I+1)-IPNTR(I)) 80 CONTINUE C C DETERMINE THE DEGREE SEQUENCE FOR THE INTERSECTION C GRAPH OF THE COLUMNS OF A. C CALL D7EGR(N,INDROW,JPNTR,INDCOL,IPNTR,IWA(5*N+1),IWA(N+1),BWA) C C COLOR THE INTERSECTION GRAPH OF THE COLUMNS OF A C WITH THE SMALLEST-LAST (SL) ORDERING. C CALL M7SLO(N,INDROW,JPNTR,INDCOL,IPNTR,IWA(5*N+1),IWA(4*N+1), * MAXCLQ,IWA(1),IWA(N+1),IWA(2*N+1),IWA(3*N+1),BWA) CALL M7SEQ(N,INDROW,JPNTR,INDCOL,IPNTR,IWA(4*N+1),NGRP,MAXGRP, * IWA(N+1),BWA) MINGRP = MAX0(MINGRP,MAXCLQ) IF (MAXGRP .EQ. MINGRP) GO TO 130 C C COLOR THE INTERSECTION GRAPH OF THE COLUMNS OF A C WITH THE INCIDENCE-DEGREE (ID) ORDERING. C CALL I7DO(M,N,INDROW,JPNTR,INDCOL,IPNTR,IWA(5*N+1),IWA(4*N+1), * MAXCLQ,IWA(1),IWA(N+1),IWA(2*N+1),IWA(3*N+1),BWA) CALL M7SEQ(N,INDROW,JPNTR,INDCOL,IPNTR,IWA(4*N+1),IWA(1),NUMGRP, * IWA(N+1),BWA) MINGRP = MAX0(MINGRP,MAXCLQ) IF (NUMGRP .GE. MAXGRP) GO TO 100 MAXGRP = NUMGRP DO 90 J = 1, N NGRP(J) = IWA(J) 90 CONTINUE IF (MAXGRP .EQ. MINGRP) GO TO 130 100 CONTINUE C C COLOR THE INTERSECTION GRAPH OF THE COLUMNS OF A C WITH THE LARGEST-FIRST (LF) ORDERING. C CALL N7MSRT(N,N-1,IWA(5*N+1),-1,IWA(4*N+1),IWA(2*N+1),IWA(N+1)) CALL M7SEQ(N,INDROW,JPNTR,INDCOL,IPNTR,IWA(4*N+1),IWA(1),NUMGRP, * IWA(N+1),BWA) IF (NUMGRP .GE. MAXGRP) GO TO 120 MAXGRP = NUMGRP DO 110 J = 1, N NGRP(J) = IWA(J) 110 CONTINUE 120 CONTINUE C C EXIT FROM PROGRAM. C 130 CONTINUE RETURN C C LAST CARD OF SUBROUTINE DSM. C END