 
      SUBROUTINE SLVBLK ( BLOKS, INTEGS, NBLOKS, B, IPIVOT, X, IFLAG )
C    THIS PROGRAM SOLVES  THE  LINEAR SYSTEM  A*X = B  WHERE A IS AN
C  ALMOST BLOCK DIAGONAL MATRIX.  SUCH ALMOST BLOCK DIAGONAL MATRICES
C  ARISE NATURALLY IN PIECEWISE POLYNOMIAL INTERPOLATION OR APPROX-
C  IMATION AND IN FINITE ELEMENT METHODS FOR TWO-POINT BOUNDARY VALUE
C  PROBLEMS.  THE PLU FACTORIZATION METHOD IS IMPLEMENTED HERE TO TAKE
C  ADVANTAGE OF THE SPECIAL STRUCTURE OF SUCH SYSTEMS FOR SAVINGS IN
C  COMPUTING TIME AND STORAGE REQUIREMENTS.
C AUTHORS:
C C. DE BOOR, MATH RESEARCH CENTER, UNIVERSITY OF WISCONSIN-MADISON
C A COMPLETE DESCRIPTION OF THE ALGORITHM IS CONTAINED IN THE PAPER
C BY THE SAME AUTHORS IN ACM TOMS V6, (MARCH 1980) PP 151.
C
C                  PARAMETERS
C  BLOKS   A ONE-DIMENSIONAL ARRAY, OF LENGTH
C                   SUM( INTEGS(1,I)*INTEGS(2,I) , I = 1,NBLOKS )
C          ON INPUT, CONTAINS THE BLOCKS OF THE ALMOST BLOCK DIAGONAL
C          MATRIX  A  .  THE ARRAY INTEGS (SEE BELOW AND THE EXAMPLE)
C          DESCRIBES THE BLOCK STRUCTURE.
C          ON OUTPUT, CONTAINS CORRESPONDINGLY THE PLU FACTORIZATION
C          OF  A  (IF IFLAG .NE. 0).  CERTAIN OF THE ENTRIES INTO BLOKS
C          ARE ARBITRARY (WHERE THE BLOCKS OVERLAP).
C  INTEGS  INTEGER ARRAY DESCRIPTION OF THE BLOCK STRUCTURE OF  A .
C            INTEGS(1,I) = NO. OF ROWS OF BLOCK I        =  NROW
C            INTEGS(2,I)= NO. OF COLUMNS OF BLOCK I      =  NCOL
C            INTEGS(3,I) = NO. OF ELIM. STEPS IN BLOCK I =  LAST
C                          I  = 1,2,...,NBLOKS
C          THE LINEAR SYSTEM IS OF ORDER
C                N  =  SUM ( INTEGS(3,I) , I=1,...,NBLOKS ),
C          BUT THE TOTAL NUMBER OF ROWS IN THE BLOCKS IS
C              NBROWS = SUM( INTEGS(1,I) , I = 1,...,NBLOKS)
C  NBLOKS  NUMBER OF BLOCKS
C  B       RIGHT SIDE OF THE LINEAR SYSTEM, ARRAY OF LENGTH NBROWS.
C          CERTAIN OF THE ENTRIES ARE ARBITRARY, CORRESPONDING TO
C          ROWS OF THE BLOCKS WHICH OVERLAP (SEE BLOCK STRUCTURE AND
C          THE EXAMPLE BELOW).
C  IPIVOT  ON OUTPUT, INTEGER ARRAY CONTAINING THE PIVOTING SEQUENCE
C          USED. LENGTH IS NBROWS
C  X       ON OUTPUT, CONTAINS THE COMPUTED SOLUTION (IF IFLAG .NE. 0)
C          LENGTH IS N.
C  IFLAG   ON OUTPUT, INTEGER
C            = (-1)**(NO. OF INTERCHANGES DURING FACTORIZATION)
C                   IF  A  IS INVERTIBLE
C            = 0    IF  A  IS SINGULAR
C
C                   AUXILIARY PROGRAMS
C  FCBLOK (BLOKS,INTEGS,NBLOKS,IPIVOT,SCRTCH,IFLAG)  FACTORS THE MATRIX
C           A , AND IS USED FOR THIS PURPOSE IN SLVBLK. ITS ARGUMENTS
C          ARE AS IN SLVBLK, EXCEPT FOR
C              SCRTCH = A WORK ARRAY OF LENGTH MAX(INTEGS(1,I)).
C
C  SBBLOK (BLOKS,INTEGS,NBLOKS,IPIVOT,B,X)  SOLVES THE SYSTEM A*X = B
C          ONCE  A  IS FACTORED. THIS IS DONE AUTOMATICALLY BY SLVBLK
C          FOR ONE RIGHT SIDE B, BUT SUBSEQUENT SOLUTIONS MAY BE
C          OBTAINED FOR ADDITIONAL B-VECTORS. THE ARGUMENTS ARE ALL
C          AS IN SLVBLK.
C
C  DTBLOK (BLOKS,INTEGS,NBLOKS,IPIVOT,IFLAG,DETSGN,DETLOG) COMPUTES THE
C          DETERMINANT OF  A  ONCE SLVBLK OR FCBLOK HAS DONE THE FACT-
C          ORIZATION.THE FIRST FIVE ARGUMENTS ARE AS IN SLVBLK.
C              DETSGN  = SIGN OF THE DETERMINANT
C              DETLOG  = NATURAL LOG OF THE DETERMINANT
C
C             ------ BLOCK STRUCTURE OF  A  ------
C  THE NBLOKS BLOCKS ARE STORED CONSECUTIVELY IN THE ARRAY  BLOKS .
C  THE FIRST BLOCK HAS ITS (1,1)-ENTRY AT BLOKS(1), AND, IF THE I-TH
C  BLOCK HAS ITS (1,1)-ENTRY AT BLOKS(INDEX(I)), THEN
C         INDEX(I+1) = INDEX(I)  +  NROW(I)*NCOL(I) .
C    THE BLOCKS ARE PIECED TOGETHER TO GIVE THE INTERESTING PART OF  A
C  AS FOLLOWS.  FOR I = 1,2,...,NBLOKS-1, THE (1,1)-ENTRY OF THE NEXT
C  BLOCK (THE (I+1)ST BLOCK ) CORRESPONDS TO THE (LAST+1,LAST+1)-ENTRY
C  OF THE CURRENT I-TH BLOCK.  RECALL LAST = INTEGS(3,I) AND NOTE THAT
C  THIS MEANS THAT
C      A. EVERY BLOCK STARTS ON THE DIAGONAL OF  A .
C      B. THE BLOCKS OVERLAP (USUALLY). THE ROWS OF THE (I+1)ST BLOCK
C         WHICH ARE OVERLAPPED BY THE I-TH BLOCK MAY BE ARBITRARILY DE-
C         FINED INITIALLY. THEY ARE OVERWRITTEN DURING ELIMINATION.
C    THE RIGHT SIDE FOR THE EQUATIONS IN THE I-TH BLOCK ARE STORED COR-
C  RESPONDINGLY AS THE LAST ENTRIES OF A PIECE OF  B  OF LENGTH  NROW
C  (= INTEGS(1,I)) AND FOLLOWING IMMEDIATELY IN  B  THE CORRESPONDING
C  PIECE FOR THE RIGHT SIDE OF THE PRECEDING BLOCK, WITH THE RIGHT SIDE
C  FOR THE FIRST BLOCK STARTING AT  B(1) . IN THIS, THE RIGHT SIDE FOR
C  AN EQUATION NEED ONLY BE SPECIFIED ONCE ON INPUT, IN THE FIRST BLOCK
C  IN WHICH THE EQUATION APPEARS.
C
C             ------ EXAMPLE AND TEST DRIVER ------
C    THE TEST DRIVER FOR THIS PACKAGE CONTAINS AN EXAMPLE, A LINEAR
C  SYSTEM OF ORDER 11, WHOSE NONZERO ENTRIES ARE INDICATED IN THE FOL-
C  LOWING SCHEMA BY THEIR ROW AND COLUMN INDEX MODULO 10. NEXT TO IT
C  ARE THE CONTENTS OF THE  INTEGS  ARRRAY WHEN THE MATRIX IS TAKEN TO
C  BE ALMOST BLOCK DIAGONAL WITH  NBLOKS = 5, AND BELOW IT ARE THE FIVE
C  BLOCKS.
C
C                      NROW1 = 3, NCOL1 = 4
C           11 12 13 14
C           21 22 23 24   NROW2 = 3, NCOL2 = 3
C           31 32 33 34
C  LAST1 = 2      43 44 45
C                 53 54 55            NROW3 = 3, NCOL3 = 4
C        LAST2 = 3         66 67 68 69   NROW4 = 3, NCOL4 = 4
C                          76 77 78 79      NROW5 = 4, NCOL5 = 4
C                          86 87 88 89
C                 LAST3 = 1   97 98 99 90
C                    LAST4 = 1   08 09 00 01
C                                18 19 10 11
C                       LAST5 = 4
C
C         ACTUAL INPUT TO BLOKS SHOWN BY ROWS OF BLOCKS OF  A .
C      (THE ** ITEMS ARE ARBITRARY, THIS STORAGE IS USED BY SLVBLK)
C
C  11 12 13 14  / ** ** **  / 66 67 68 69  / ** ** ** **  / ** ** ** **
C  21 22 23 24 /  43 44 45 /  76 77 78 79 /  ** ** ** ** /  ** ** ** **
C  31 32 33 34/   53 54 55/   86 87 88 89/   97 98 99 90/   08 09 00 01
C                                                           18 19 10 11
C
C  INDEX = 1      INDEX = 13  INDEX = 22     INDEX = 34     INDEX = 46
C
C         ACTUAL RIGHT SIDE VALUES WITH ** FOR ARBITRARY VALUES
C  B1 B2 B3 ** B4 B5 B6 B7 B8 ** ** B9 ** ** B10 B11
C
C  (IT WOULD HAVE BEEN MORE EFFICIENT TO COMBINE BLOCK 3 WITH BLOCK 4)
C
