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;