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