NUMAL Section 3.1.2.1.1.2.1.1
BEGIN SECTION : 3.1.2.1.1.2.1.1 (December, 1975)
AUTHOR : T.J. DEKKER.
CONTRIBUTOR : J. KOK.
INSTITUTE : MATHEMATICAL CENTRE.
RECEIVED : 731001.
BRIEF DESCRIPTION :
THIS SECTION CONTAINS THE PROCEDURE CHLDECBND
FOR THE CHOLESKY DECOMPOSITION OF A SYMMETRIC POSITIVE DEFINITE
BAND MATRIX.
KEYWORDS :
LINEAR EQUATIONS,
CHOLESKY DECOMPOSITION,
SYMMETRIC POSITIVE DEFINITE MATRIX,
BAND MATRIX.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS :
"PROCEDURE" CHLDECBND(A, N, W, AUX); "VALUE" N, W; "INTEGER" N, W;
"ARRAY" A, AUX;
"CODE" 34330;
THE MEANING OF THE FORMAL PARAMETERS IS :
A : <ARRAY IDENTIFIER>;
"ARRAY" A[1 : W * (N - 1) + N];
ENTRY : A CONTAINS COLUMNWISE (I.E. THE (I,J)-TH
ELEMENT OF THE MATRIX IS A[(J-1)*W+I], J=1,..,N,
I=MAX(1,J-W),..,J) THE UPPER-TRIANGULAR BAND
ELEMENTS OF THE SYMMETRIC BAND MATRIX;
EXIT : THE BAND ELEMENTS OF THE CHOLESKY
MATRIX, WHICH IS AN UPPER-TRIANGULAR BAND MATRIX WITH
W SUPERDIAGONALS, ARE DELIVERED COLUMNWISE IN A;
N : <ARITHMETIC EXPRESSION>;
ORDER OF THE BAND MATRIX;
W : <ARITHMETIC EXPRESSION>;
NUMBER OF SUPERDIAGONALS OF THE MATRIX;
AUX : <ARRAY IDENTIFIER>;
"ARRAY" AUX[2 : 3];
ENTRY : AUX[2] IS A RELATIVE TOLERANCE TO CONTROL THE
CALCULATION OF THE DIAGONAL ELEMENTS OF THE
CHOLESKY MATRIX (SEE METHOD AND PERFORMANCE);
NORMAL EXIT :
AUX[3] = N;
ABNORMAL EXIT :
AUX[3] = K - 1, WHERE K IS THE INDEX OF THE DIAGONAL
ELEMENT OF THE CHOLESKY MATRIX THAT CANNOT BE
CALCULATED.
PROCEDURES USED :
VECVEC = CP34010.
RUNNING TIME :
(C1 * W + C2) * W * N;
THE CONSTANTS C1 AND C2 DEPEND UPON THE
ARITHMETIC OF THE COMPUTER.
LANGUAGE : ALGOL 60.
METHOD AND PERFORMANCE :
CHLDECBND PERFORMS THE CHOLESKY DECOMPOSITION OF A SYMMETRIC
POSITIVE DEFINITE MATRIX, WHOSE NON-ZERO ELEMENTS ARE IN BAND FORM,
AND WHOSE UPPER-TRIANGULAR BAND ELEMENTS ARE STORED COLUMNWISE IN
IONAL ARRAY.
THE METHOD USED IS CHOLESKY'S SQUARE ROOT METHOD. IF THE GIVEN
MATRIX IS POSITIVE DEFINITE, THEN THIS METHOD YIELDS AN UPPER-
TRIANGULAR BAND MATRIX, THE CHOLESKY MATRIX. THE NUMBER OF
NON-ZERO SUPERDIAGONALS OF THE GIVEN MATRIX AND ITS CHOLESKY
MATRIX ARE EQUAL. THE PROCESS IS COMPLETED IN N STAGES, AT EACH
STAGE PRODUCING A ROW OF THE CHOLESKY MATRIX. HOWEVER, THE
PROCESS IS DISCONTINUED IF AT SOME STAGE, SAY K, THE K-TH DIAGONAL
ELEMENT OF THE GIVEN MATRIX MINUS THE SUM OF SQUARES OF THE
SUPERDIAGONAL ELEMENTS OF THE K-TH COLUMN OF THE CHOLESKY MATRIX
(THE SQUARE ROOT OF THIS QUANTITY BEING THE K-TH DIAGONAL ELEMENT
OF THE CHOLESKY MATRIX) IS EITHER NEGATIVE OR LESS THAN A GIVEN
RELATIVE TOLERANCE (AUX[2]) TIMES THE MAXIMAL DIAGONAL ELEMENT
THE GIVEN MATRIX. IN THIS CASE THE GIVEN MATRIX, POSSIBLY MODIFIED
BY ROUNDING ERRORS, IS NOT POSITIVE DEFINITE. THIS IS INDICATED IN
AUX[3], BY WHICH THE VALUE K - 1 IS DELIVERED. IF THE
DECOMPOSITION IS CARRIED OUT FULLY, AUX[3] BECOMES N.
THE PROCEDURE DELIVERS THE BAND ELEMENTS OF THE CHOLESKY MATRIX.
SEE ALSO REF [1], SECTION 222.
REFERENCE :
[1] DEKKER, T.J. :
ALGOL 60 PROCEDURES IN NUMERICAL ALGEBRA, PART 1,
MC TRACT 22, 1968, MATHEMATISCH CENTRUM, AMSTERDAM.
EXAMPLE OF USE :
SEE EXAMPLE OF USE OF CHLSOLBND.
SOURCE TEXT(S) :
"CODE" 34330;