NUMAL Section 3.1.1.1.1.2.3

BEGIN SECTION : 3.1.1.1.1.2.3 (May, 1974)

AUTHOR: T.J. DEKKER.

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

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED: 731015.

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS FOUR PROCEDURES:
    A) CHLSOL2, FOR THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS IF THE
    COEFFICIENT MATRIX HAS BEEN DECOMPOSED BY A CALL OF THE PROCEDURE
    CHLDEC2, SECTION 3.1.1.1.1.2.1., OR CHLDECSOL2;
    B) CHLSOL1, FOR THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS IF THE
    COEFFICIENT MATRIX HAS BEEN DECOMPOSED BY A CALL OF THE PROCEDURE
    CHLDEC1, SECTION 3.1.1.1.1.2.1., OR CHLDECSOL1;
    C) CHLDECSOL2, FOR THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS BY
    CHOLESKY'S SQUARE ROOT METHOD;
    THE COEFFICIENT MATRIX HAS TO BE SYMMETRIC POSITIVE DEFINITE AND
    MUST BE GIVEN IN THE UPPER TRIANGLE OF A TWO-DIMENSIONAL ARRAY;
    D) CHLDECSOL1, FOR THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS BY
    CHOLESKY'S SQUARE ROOT METHOD;
    THE COEFFICIENT MATRIX HAS TO BE SYMMETRIC POSITIVE DEFINITE AND
    MUST BE GIVEN COLUMNWISE IN A ONE-DIMENSIONAL ARRAY.

KEYWORDS:

    LINEAR EQUATIONS,
    POSITIVE DEFINITE SYMMETRIC MATRIX,
    CHOLESKY DECOMPOSITION.


SUBSECTION: CHLSOL2.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE IS:
    "PROCEDURE" CHLSOL2(A, N, B); "VALUE" N; "INTEGER" N; "ARRAY" A, B;
    "CODE" 34390;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:      <ARRAY IDENTIFIER>;
            "ARRAY" A[1:N,1:N];
            ENTRY: THE  UPPER-TRIANGULAR PART OF THE  CHOLESKY MATRIX
                   AS  PRODUCED BY CHLDEC2, SECTION  3.1.1.1.1.2.1., OR
                   CHLDECSOL2  (THIS  SECTION), MUST  BE  GIVEN IN  THE
                   UPPER TRIANGLE OF A;
            EXIT:  THE CONTENTS OF A ARE NOT CHANGED;
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE MATRIX;
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            ENTRY: THE  RIGHT HAND   SIDE  OF  THE   SYSTEM  OF  LINEAR
                   EQUATIONS;
            EXIT:  THE SOLUTION OF THE SYSTEM.

PROCEDURES USED:

    MATVEC = CP34011,
    TAMVEC = CP34012.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N SQUARED.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE:

    THE PROCEDURE CHLSOL2 CALCULATES THE SOLUTION OF A SYSTEM OF LINEAR
    EQUATIONS, PROVIDED THAT THE COEFFICIENT MATRIX HAS BEEN DECOMPOSED
    BY A SUCCESSFUL CALL OF CHLDEC2 OR CHLDECSOL2;
    THE SOLUTION IS OBTAINED BY CARRYING OUT THE FORWARD AND BACK
    SUBSTITUTION WITH THE CHOLESKY MATRIX AND THE RIGHT HAND SIDE.
    THE RIGHT HAND SIDE IS OVERWRITTEN BY THE SOLUTION BUT THE
    ELEMENTS OF THE CHOLESKY MATRIX ARE NOT CHANGED, THUS SEVERAL
    SYSTEMS OF LINEAR EQUATIONS WITH THE SAME COEFFICIENT MATRIX BUT
    DIFFERENT RIGHT HAND SIDES CAN BE SOLVED BY SUCCESSIVE CALLS OF
    CHLSOL2. SEE ALSO REF [1].

REFERENCES:

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

EXAMPLE OF USE:

    SEE EXAMPLE OF USE OF CHLINV2, SECTION 3.1.1.1.1.2.4.


SUBSECTION: CHLSOL1.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE IS:
    "PROCEDURE" CHLSOL1(A, N, B); "VALUE" N; "INTEGER" N; "ARRAY" A, B;
    "CODE" 34391;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:      <ARRAY IDENTIFIER>;
            "ARRAY" A[1 : (N + 1) * N // 2];
            ENTRY: THE  UPPER-TRIANGULAR PART OF THE  CHOLESKY MATRIX
                   AS  PRODUCED BY CHLDEC1, SECTION  3.1.1.1.1.2.1., OR
                   CHLDECSOL1 (THIS SECTION), MUST  BE GIVEN COLUMNWISE
                   IN ARRAY A;
            EXIT:  THE CONTENTS OF A ARE NOT CHANGED;
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE MATRIX;
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            ENTRY: THE  RIGHT HAND   SIDE  OF  THE   SYSTEM  OF  LINEAR
                   EQUATIONS;
            EXIT:  THE SOLUTION OF THE SYSTEM.

PROCEDURES USED:

    VECVEC = CP34010,
    SEQVEC = CP34016.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N SQUARED.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE:

    THE PROCEDURE CHLSOL1 CALCULATES THE SOLUTION OF A SYSTEM OF LINEAR
    EQUATIONS, PROVIDED THAT THE COEFFICIENT MATRIX HAS BEEN DECOMPOSED
    BY A SUCCESSFUL CALL OF CHLDEC1 OR CHLDECSOL1;
    SEVERAL SYSTEMS WITH THE SAME COEFFICIENT MATRIX BUT DIFFERENT
    RIGHT HAND SIDES CAN BE SOLVED BY SUCCESSIVE CALLS OF CHLSOL1.
    SEE ALSO METHOD AND PERFORMANCE OF CHLSOL2 (THIS SECTION).

EXAMPLE OF USE:

    SEE EXAMPLE OF USE OF CHLINV1, SECTION 3.1.1.1.1.2.4.


SUBSECTION: CHLDECSOL2.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE IS:
    "PROCEDURE" CHLDECSOL2(A, N, AUX, B); "VALUE" N; "INTEGER" N;
    "ARRAY" A, AUX, B;
    "CODE" 34392;

    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; (SEE METHOD
                   AND PERFORMANCE OF CHLDEC2, SECTION 3.1.1.1.1.2.1);
            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.
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            ENTRY: THE  RIGHT HAND   SIDE  OF  THE   SYSTEM  OF  LINEAR
                   EQUATIONS;
            EXIT:  THE SOLUTION OF THE SYSTEM.

PROCEDURES USED:
    CHLDEC2 = CP34310,
    CHLSOL2 = CP34390.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE:

    THE PROCEDURE CHLDECSOL2 SOLVES A SYSTEM OF LINEAR EQUATIONS WITH
    A SYMMETRIC POSITIVE DEFINITE COEFFICIENT MATRIX BY CALLING
    CHLDEC2, SECTION 3.1.1.1.1.2.1., AND, IF THIS CALL WAS
    SUCCESSFUL, CHLSOL2 (THIS SECTION).
    SEE ALSO CHLDEC2, SECTION 3.1.1.1.1.2.1.

EXAMPLE OF USE:

    SEE EXAMPLE OF USE OF CHLDECINV2, SECTION 3.1.1.1.1.2.4.


SUBSECTION: CHLDECSOL1.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE IS:
    "PROCEDURE" CHLDECSOL1(A, N, AUX, B); "VALUE" N; "INTEGER" N;
    "ARRAY" A, AUX, B;
    "CODE" 34393;

    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.
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            ENTRY: THE  RIGHT HAND   SIDE  OF  THE   SYSTEM  OF  LINEAR
                   EQUATIONS;
            EXIT:  THE SOLUTION OF THE SYSTEM.

PROCEDURES USED:

    CHLDEC1 = CP34311,
    CHLSOL1 = CP34391.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE:
    THE PROCEDURE CHLDECSOL1 SOLVES A SYSTEM OF LINEAR EQUATIONS WITH
    A SYMMETRIC POSITIVE DEFINITE COEFFICIENT MATRIX BY CALLING
    CHLDEC1, SECTION 3.1.1.1.1.2.1., AND, IF THIS CALL WAS
    SUCCESSFUL, CHLSOL1 (THIS SECTION).
    THE UPPER TRIANGLE OF THE COEFFICIENT MATRIX MUST BE STORED COLUMN-
    WISE IN A ONE-DIMENSIONAL ARRAY.
    SEE ALSO CHLDEC1, SECTION 3.1.1.1.1.2.1.

EXAMPLE OF USE:
    SEE EXAMPLE OF USE OF CHLDECINV1, SECTION 3.1.1.1.1.2.4.

SOURCE TEXT(S) :

"CODE" 34390;
"CODE" 34391;
"CODE" 34392;
"CODE" 34393;