NUMAL Section 3.1.1.1.1.2.1

BEGIN SECTION : 3.1.1.1.1.2.1 (May, 1974)

AUTHOR: T.J. DEKKER.

CONTRIBUTORS: S.P.N. VAN KAMPEN, J. KOK.

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED: 731015.

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS TWO PROCEDURES:
    A) CHLDEC2 CALCULATES THE CHOLESKY  DECOMPOSITION OF A POSITIVE
    DEFINITE SYMMETRIC MATRIX WH0SE UPPER TRIANGLE IS GIVEN IN A TWO-
    DIMENSIONAL ARRAY;
    B) CHLDEC1 CALCULATES THE CHOLESKY  DECOMPOSITION OF A POSITIVE
    DEFINITE SYMMETRIC MATRIX WHOSE UPPER TRIANGLE IS GIVEN COLUMNWISE
    IN A ONE-DIMENSIONAL ARRAY.

KEYWORDS:

    LINEAR EQUATIONS,
    POSITIVE DEFINITE SYMMETRIC MATRIX,
    CHOLESKY DECOMPOSITION.


SUBSECTION: CHLDEC2.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE IS:
    "PROCEDURE" CHLDEC2(A, N, AUX); "VALUE" N; "INTEGER" N;
    "ARRAY" A, AUX;
    "CODE" 34310;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:      <ARRAY IDENTIFIER>;
            "ARRAY" A[1:N,1:N];
            ENTRY: THE UPPER  TRIANGLE OF THE  POSITIVE DEFINITE MATRIX
                   MUST BE GIVEN IN THE UPPER-TRIANGULAR PART OF A (THE
                   ELEMENTS A[I,J], I <= J);
            EXIT:  THE  CHOLESKY  DECOMPOSITION  OF   THE  MATRIX  IS
                   DELIVERED IN THE UPPER TRIANGLE OF A;
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE MATRIX;
    AUX:    <ARRAY IDENTIFIER>;
            "ARRAY" AUX[2:3];
            ENTRY: AUX[2]: A  RELATIVE TOLERANCE  USED TO  CONTROL  THE
                   CALCULATION OF THE DIAGONAL ELEMENTS;
            NORMAL EXIT:   AUX[3]:= N;
            ABNORMAL EXIT: IF THE  DECOMPOSITION CANNOT BE  CARRIED OUT
                   BECAUSE  THE  MATRIX  IS (NUMERICALLY) NOT  POSITIVE
                   DEFINITE,  AUX[3]:= K - 1, WHERE K IS THE LAST STAGE
                   NUMBER.

PROCEDURES USED: TAMMAT = CP34014.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    CHLDEC2 PERFORMS THE CHOLESKY DECOMPOSITION OF A SYMMETRIC
    POSITIVE DEFINITE MATRIX.
    THE METHOD USED IS CHOLESKY'S SQUARE ROOT METHOD WITHOUT
    PIVOTING (SEE REF[1] AND [2]). IF THE GIVEN SYMMETRIC MATRIX IS
    POSITIVE DEFINITE, THE METHOD YIELDS AN UPPER-TRIANGULAR MATRIX U
    SUCH THAT U'U EQUALS THE GIVEN MATRIX.
    THE PROCESS IS TERMINATED AT STAGE K, IF THE K-TH DIAGONAL ELEMENT
    OF THE GIVEN MATRIX MINUS THE SUM OF THE SQUARED ELEMENTS OF THE
    K-TH COLUMN OF U IS LESS THAN A TOLERANCE (AUX[2]) TIMES THE
    MAXIMAL DIAGONAL ELEMENT OF THE GIVEN MATRIX. IN THIS CASE THE
    MATRIX, POSSIBLY MODIFIED BY ROUNDING ERRORS, IS NOT POSITIVE
    DEFINITE.

REFERENCES:

    [1]. T.J. DEKKER.
         ALGOL 60 PROCEDURES IN NUMERICAL ALGEBRA, PART 1.
         MC TRACT 22, 1968, MATH. CENTR., AMSTERDAM.

    [2]. J.H. WILKINSON.
         THE ALGEBRAIC EIGENVALUE PROBLEM.
         CLARENDON PRESS, OXFORD, 1965.

EXAMPLE OF USE:

    SEE EXAMPLE OF USE OF CHLINV2, SECTION 3.1.1.1.1.2.4.


SUBSECTION: CHLDEC1.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE IS:
    "PROCEDURE" CHLDEC1(A, N, AUX); "VALUE" N; "INTEGER" N;
    "ARRAY" A, AUX;
    "CODE" 34311;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:      <ARRAY IDENTIFIER>;
            "ARRAY" A[1 : (N + 1) * N // 2];
            ENTRY: THE UPPER-TRIANGULAR PART OF THE  POSITIVE  DEFINITE
                   SYMMETRIC MATRIX MUST BE GIVEN COLUMNWISE IN ARRAY A
                   (THE (I,J)-TH ELEMENT OF THE MATRIX MUST BE GIVEN IN
                   A[(J - 1) * J // 2 + I] FOR 1 <= I <= J <= N);
            EXIT:  THE  CHOLESKY  DECOMPOSITION  OF  THE   MATRIX  IS
                   DELIVERED COLUMNWISE IN A.
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE MATRIX;
    AUX:    <ARRAY IDENTIFIER>;
            "ARRAY" AUX[2:3];
            ENTRY: AUX[2]: A  RELATIVE TOLERANCE  USED TO  CONTROL  THE
                   CALCULATION OF THE DIAGONAL ELEMENTS;
            NORMAL EXIT:   AUX[3]:= N;
            ABNORMAL EXIT: IF THE  DECOMPOSITION CANNOT BE  CARRIED OUT
                   BECAUSE  THE  MATRIX  IS (NUMERICALLY) NOT  POSITIVE
                   DEFINITE,  AUX[3]:= K - 1, WHERE K IS THE LAST STAGE
                   NUMBER.

PROCEDURES USED: VECVEC = CP34010.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE:

    CHLDEC1 PERFORMS THE CHOLESKY DECOMPOSITION OF A SYMMETRIC
    POSITIVE DEFINITE MATRIX, WHOSE UPPER TRIANGLE IS STORED IN A ONE-
    DIMENSIONAL ARRAY, BY CHOLESKY'S SQUARE ROOT METHOD WITHOUT
    PIVOTING.
    SEE ALSO METHOD AND PERFORMANCE OF CHLDEC2, (THIS SECTION).

EXAMPLE OF USE:

    SEE EXAMPLE OF USE OF CHLINV1, SECTION 3.1.1.1.1.2.4.

SOURCE TEXT(S) :

"CODE" 34310;

"CODE" 34311;