End of file
Contents
Index



The Cholesky Decomposition for Band Matrices


      SUBROUTINE CHOBND (N, M, AP, RS, X, IFLAG, Z)
C
C*****************************************************************
C                                                                *
C  CHOBND solves a linear system of equations                    *
C                 A * X = RS                                     *
C  for a symmetric, positive definite banded matrix A in         *
C  condensed form using the Cholesky method.                     *
C                                                                *
C                                                                *
C  INPUT PARAMETERS:                                             *
C  =================                                             *
C  N      : number of rows of A                                  *
C  M      : number of nonzero codiagonals of A                   *
C  AP     : array AP(1:N,1:M+1), containing the upper triangular *
C           entries of A in condensed form.                      *
C           The condensation of A is achieved by shifting the    *
C           rows of A successively to the left until the diagonal*
C           and upper codiagonals of A appear as columns.        *
C           The main diagonal of A forms the first column of the *
C           condensed matrix; the first codiagonal is in its     *
C           second column, its last element is set equal to zero;*
C           etc. until the (M+1)-st column of the condensed      *
C           matrix contains the M-th codiagonal of A in positions*
C           1 to N-M and zeros below.                            *
C           The following code will condense a matrix A into AP: *
C                  DO 10 I=1,N                                   *
C                     DO 20 K=I,MIN(N,I+M)                       *
C                        AP(I,K-I+1) = A(I,K)                    *
C               20    CONTINUE                                   *
C               10 CONTINUE                                      *
C                                                                *
C  RS     : N-vector RS(1:N), the right hand side of the system  *
C                                                                *
C                                                                *
C  OUTPUT PARAMETERS:                                            *
C  ==================                                            *
C  AP     : Same as A, but overwritten with the Cholesky factors *
C           R(TRANS)*D*R in condensed form: R is an upper band   *
C           triangular matrix with unit diagonal and M bands,    *
C           D is a diagonal matrix.                              *
C           The diagonal entries of D form the first column of   *
C           AP, successive columns of AP contain the codiagonals *
C           of R. The unit diagonal of R is not stored and       *
C           neither is R(TRANS).                                 *
C  X      : N-vector X(1:N), the solution vector                 *
C  IFLAG  :  error parameter:                                    *
C            1: all is ok                                        *
C            0: Matrix is numerically singular                   *
C           -1: Matrix is numerically not positive definite      *
C                                                                *
C           If  IFLAG = 1, the  determinant of A is given by:    *
C              DET(A) = AP(1,1) * AP(2,1) * ... * AP(N,1)        *
C                                                                *
C                                                                *
C  AUXILIARY PARAMETER:                                          *
C  ====================                                          *
C  Z      : N-vector Z(1:N)                                      *
C                                                                *
C----------------------------------------------------------------*
C                                                                *
C  Required subroutines:                                         *
C                                                                *
C  CHOBDZ  Cholesky factorization of AP                          *
C  CHOBDL  Updating and backsustitution                          *
C  MACHPD  machine constant                                      *
C                                                                *
C*****************************************************************
C                                                                *
C  Author     : Elmar Pohl                                       *
C  Date       : 11.15.1991                                       *
C  Sourcee    : FORTRAN 77                                       *
C                                                                *
C*****************************************************************
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
      DIMENSION AP(1:N,1:M+1), RS(1:N), X(1:N), Z(1:N)
C
C     Factor  A = R(TRANS)*D*R
C
      CALL CHOBDZ(N, M, AP, IFLAG, Z)
C
C     Updating and backsubstitution
C
      IF (IFLAG .EQ. 1) CALL CHOBDL(N, M, AP, RS, X, Z)
C
      RETURN
      END
C
C

      SUBROUTINE CHOBDL (N, M, AP, RS, X, Z)
C
C*****************************************************************
C                                                                *
C  CHOBDL solves a linear system of equations                    *
C                 A * X = RS                                     *
C  for a symmetric, positive definite banded matrix A in         *
C  condensed form using the Cholesky method.                     *
C  Here the matrix A has been overwritten in AP by the subroutine*
C  CHOBDZ with its Cholesky factors  A = R(TRANS)*D*R  in        *
C  condensed form.                                               *
C                                                                *
C                                                                *
C  INPUT PARAMETERS:                                             *
C  =================                                             *
C  N      : number of rows of AP                                 *
C  M      : number of nonzero codiagonals of A                   *
C  AP     : array AP(1:N,1:M+1), the output of SUBROUTINE CHOBDZ *
C           with the Cholesky factors of A in condensed form.    *
C  RS     : N-vector RS(1:N), the right hand side of the system  *
C                                                                *
C                                                                *
C  OUTPUT PARAMETERS:                                            *
C  ==================                                            *
C                                                                *
C  X      : N-vector X(1:N), the solution vector                 *
C                                                                *
C                                                                *
C  AUXILIARY PARAMETER:                                          *
C  ====================                                          *
C  Z      : N-vector Z(1:N)                                      *
C                                                                *
C----------------------------------------------------------------*
C                                                                *
C  Required subroutines: none                                    *
C                                                                *
C*****************************************************************
C                                                                *
C  Author     : Elmar Pohl                                       *
C  Date       : 11.15.1991                                       *
C  Sourcee    : FORTRAN 77                                       *
C                                                                *
C*****************************************************************
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
      DIMENSION AP(1:N, 1:M+1), RS(1:N), X(1:N), Z(1:N)
C
C     Solve  R(TRANS) * Z = RS
C
      DO 10 J = 1, N
         Z(J) = RS(J)
         DO 20 I = MAX0(1, J - M), J - 1
            Z(J) = Z(J) - AP(I, J - I + 1) * Z(I)
   20    CONTINUE
   10 CONTINUE
C
C     Solve  R * X = D^-1 * Z
C
      DO 30 I = N, 1, -1
         X(I) = Z(I) / AP(I, 1)
         DO 40 J = I + 1, MIN0(N, I + M)
            X(I) = X(I) - AP(I, J - I + 1) * X(J)
   40    CONTINUE
   30 CONTINUE
      RETURN
      END
C
C

      SUBROUTINE CHOBDZ (N, M, AP, IFLAG, Z)
C
C*****************************************************************
C                                                                *
C  CHOBDZ factors a symmetric, positive definite banded matrix AP*
C  given in condensed form into  R(TRANS)*D*R  using the         *
C  Cholesky method. Here D is a diagonal matrix and R is a unit  *
C  diagonal upper tringular banded matrix with as many           *
C  codiagonals as the original A. The output is again stored in  *
C  condensed form with D in the first column and the codiagonal  *
C  bands of R in subsequent columns.                             *
C                                                                *
C                                                                *
C  INPUT PARAMETERS:                                             *
C  =================                                             *
C  N      : number of rows of AP                                 *
C  M      : number of codiagonals in A                           *
C  AP     : array AP(1:N,1:M+1), containing the upper triangle   *
C           of A in condensed form. For a code that achieves this*
C           for a given symmetric matrix, see CHOBND.            *
C                                                                *
C                                                                *
C  OUTPUT PARAMETERS:                                            *
C  ==================                                            *
C  AP     : Same as A, but overwritten with the Cholesky factors *
C           R(TRANS)*D*R in condensed form: R is an upper band   *
C           triangular matrix with unit diagonal and M bands,    *
C           D is a diagonal matrix.                              *
C           The diagonal entries of D form the first column of   *
C           AP, successive columns of AP contain the codiagonals *
C           of R. The unit diagonal of R is not stored and       *
C           neither is R(TRANS).                                 *
C  X      : N-vector X(1:N), the solution vector                 *
C  IFLAG  :  error parameter:                                    *
C            1: all is ok                                        *
C            0: Matrix is numerically singular                   *
C           -1: Matrix is numerically not positive definite      *
C                                                                *
C                                                                *
C  AUXILIARY PARAMETERS:                                         *
C  ====================                                          *
C  Z      : N-vector Z(1:N)                                      *
C                                                                *
C----------------------------------------------------------------*
C                                                                *
C  Required subroutines:                                         *
C                                                                *
C  MACHPD  Machine constant                                      *
C                                                                *
C*****************************************************************
C                                                                *
C  Author    : Elmar Pohl                                        *
C  Date      : 11.15.1991                                        *
C  Source    : FORTRAN 77                                        *
C                                                                *
C*****************************************************************
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
      DIMENSION AP(1:N,1:M+1), Z(1:N)
C
C     Find the machine constant
C
      FMACHP = 1.0D0
   10 FMACHP = 0.5D0 * FMACHP
      IF (MACHPD(1.0D0 + FMACHP) .EQ. 1) GOTO 10
      FMACHP = FMACHP * 2.0D0
C
C     Set a bound for the relative accuracy
C
      EPS = 4.0D0 * FMACHP
C
C     Store row sum moduli of each row in Z,
C     use Z to check nonsingularity later
C
      DO 20 I = 1, N
         S = 0.0D0
         DO 30 K = I, MIN0(N, I + M)
            S = S + DABS(AP(I, K - I + 1))
   30    CONTINUE
         DO 40 K = MAX0(1, I - M), I - 1
            S = S + DABS(AP(K, I - K + 1))
   40    CONTINUE
         IF (S .EQ. 0.0D0) THEN
            IFLAG = 0
            RETURN
         END IF
         Z(I) = S
   20 CONTINUE
C
C     Cholesky decomposition
C
      DO 50 J = 1, N
         DO 60 I = MAX0(1, J - M), J - 1
               H = AP(I, J - I + 1)
               AP(I, J - I + 1) = H / AP(I, 1)
               DO 70 K = I + 1, J
                  AP(K, J - K + 1) = AP(K, J - K + 1) -
     +                               H * AP(I, K - I + 1)
   70          CONTINUE
   60    CONTINUE
         IF (AP(J, 1) .LT. 0.0D0) THEN
            IFLAG = -1
            RETURN
         ELSE IF (DABS(AP(J, 1)) / Z(J) .LE. EPS) THEN
            IFLAG = 0
            RETURN
         END IF
   50 CONTINUE
C
      IFLAG = 1
      RETURN
      END


Begin of file
Contents
Index