NUMAL Section 3.1.2.1.1.2.1.3

BEGIN SECTION : 3.1.2.1.1.2.1.3 (December, 1975)

AUTHOR      :    T.J. DEKKER.

CONTRIBUTOR :    J. KOK.

INSTITUTE   :    MATHEMATICAL CENTRE.

RECEIVED    :    731001.

BRIEF DESCRIPTION  :
    THIS SECTION CONTAINS TWO PROCEDURES.
    A) CHLSOLBND, FOR THE SOLUTION OF ONE OR MORE SYSTEMS OF LINEAR
    EQUATIONS WITH THE SAME COEFFICIENT MATRIX, WHICH IS SYMMETRIC,
    POSITIVE DEFINITE AND IN BANDFORM, PROVIDED THAT THIS
    MATRIX HAS BEEN DECOMPOSED BY A CALL OF THE PROCEDURE CHLDECBND
    (SECTION 3.1.2.1.1.2.1.1.).
    B) CHLDECSOLBND, FOR THE SOLUTION OF ONE SYSTEM OF LINEAR
    EQUATIONS BY CHOLESKY'S SQUARE ROOT METHOD, PROVIDED THAT THE
    SYMMETRIC POSITIVE DEFINITE COEFFICIENT MATRIX IS IN BAND FORM
    AND IS STORED COLUMNWISE IN A ONE-DIMENSIONAL ARRAY.

KEYWORDS  :
    LINEAR EQUATIONS,
    CHOLESKY DECOMPOSITION,
    SYMMETRIC POSITIVE DEFINITE MATRIX,
    BAND MATRIX.


SUBSECTION :    CHLSOLBND.

CALLING SEQUENCE  :

    THE HEADING OF THE PROCEDURE IS :
    "PROCEDURE" CHLSOLBND(A, N, W, B); "VALUE" N, W; "INTEGER" N, W;
    "ARRAY" A, B;
    "CODE" 34332;

    THE MEANING OF THE FORMAL PARAMETERS IS :
        A, N, W :   SEE 'CALLING SEQUENCE' OF CHLDECBND,
                THE CONTENTS OF THE ARRAY A ARE AS PRODUCED BY
                CHLDECBND;
        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,
    SCAPRD1= CP34017.

RUNNING TIME:

    (C3 * W + C4) * N;
    THE CONSTANTS C3 AND C4 DEPEND UPON THE
    ARITHMETIC OF THE COMPUTER.

LANGUAGE    :    ALGOL 60.

METHOD AND PERFORMANCE :
    THE PROCEDURE CHLSOLBND CALCULATES THE SOLUTION OF A SYSTEM OF
    LINEAR EQUATIONS, PROVIDED THAT THE COEFFICIENT MATRIX WAS
    DECOMPOSED BY A SUCCESSFUL CALL OF CHLDECBND (SECTION
    3.1.2.1.1.2.1.1.).
    THE SOLUTION OF THE LINEAR SYSTEM IS OBTAINED BY CARRYING OUT THE
    FORWARD AND BACK SUBSTITUTION WITH THE CHOLESKY MATRIX AND THE
    RIGHT HAND SIDE. THE LATTER IS OVERWRITTEN BY THE SOLUTION.
    THE SOLUTIONS OF SEVERAL SYSTEMS WITH THE SAME COEFFICIENT MATRIX
    CAN BE OBTAINED BY SUCCESSIVE CALLS OF CHLSOLBND.

EXAMPLE OF USE :

    THE FOLLOWING PROGRAM SOLVES THE SYSTEM OF SIMULTANEOUS EQUATIONS

        2 * X1   -   X2                             = 1
        -   X1 + 2 * X2   -   X3                    = 0
                 -   X2 + 2 * X3   -   X4           = 0
                          -   X3 + 2 * X4   -   X5  = 0
                                   -   X4 + 2 * X5  = 1

    "BEGIN""COMMENT" 730829, TEST CHLDECBND, CHLSOLBND AND
       CHLDETERMBND;
       "INTEGER" I;
       "ARRAY" SYMBAND[1 : 9], RIGHT[1 : 5], AUX[2 : 3];
       "FOR" I:= 1 "STEP" 1 "UNTIL" 9 "DO"
       SYMBAND[I]:= "IF" I // 2 * 2 < I "THEN" 2 "ELSE" - 1;
       RIGHT[1]:= RIGHT[5]:= 1;
       "FOR" I:= 2, 3, 4 "DO" RIGHT[I]:= 0; AUX[2]:= "- 12;
       CHLDECBND(SYMBAND, 5, 1, AUX);
       "IF" AUX[3] = 5 "THEN"
       "BEGIN" CHLSOLBND(SYMBAND, 5, 1, RIGHT);
          OUTPUT(61, "("5(+2Z.4D2B), /"("DETERMINANT IS  ")" +.8D"+DD
          ")", RIGHT, CHLDETERMBND(SYMBAND, 5, 1))
       "END"
    "END".

    THIS PROGRAM DELIVERS:
     +1.0000   +1.0000   +1.0000   +1.0000   +1.0000
    DETERMINANT IS  +.60000000"+01


SUBSECTION :    CHLDECSOLBND.

CALLING SEQUENCE :

    THE HEADING OF THE PROCEDURE IS :

    "PROCEDURE" CHLDECSOLBND(A, N, W, AUX, B); "VALUE" N, W;
    "INTEGER" N, W; "ARRAY" A, AUX, B;
    "CODE" 34333;

    THE MEANING OF THE FORMAL PARAMETERS IS :

        A, N, W, AUX    : SEE CHLDECBND;
        B               : SEE CHLSOLBND.

PROCEDURES USED :

    CHLDECBND = CP34330,
    CHLSOLBND = CP34332.

RUNNING TIME:

    (C1 * W + C5) * W * N;
    THE CONSTANTS C1 AND C5 DEPEND UPON THE ELEMENTARY
    ARITHMETIC OF THE COMPUTER.

LANGUAGE    :    ALGOL 60.

METHOD AND PERFORMANCE :

    CHLDECSOLBND SOLVES A SYSTEM OF LINEAR EQUATIONS BY CALLING
    CHLDECBND AND, PROVIDED THAT THE CHOLESKY DECOMPOSITION WAS
    SUCCESSFUL, CHLSOLBND. THE COEFFICIENT MATRIX OF THIS SYSTEM HAS TO
    BE A SYMMETRIC POSITIVE DEFINITE BAND MATRIX WHOSE UPPER-TRIANGULAR
    BAND ELEMENTS ARE STORED COLUMNWISE IN IONAL ARRAY.

EXAMPLE OF USE :

    THE PROGRAM

    "BEGIN""COMMENT" 730829, TEST CHLDECSOLBND AND CHLDETERMBND;
       "INTEGER" I;
       "ARRAY" SYMBAND[1 : 9], RIGHT[1 : 5], AUX[2 : 3];

       "FOR" I:= 1 "STEP" 1 "UNTIL" 9 "DO"
       SYMBAND[I]:= "IF" I // 2 * 2 < I "THEN" 2 "ELSE" - 1;
       RIGHT[1]:= RIGHT[5]:= 1;
       "FOR" I:= 2, 3, 4 "DO" RIGHT[I]:= 0; AUX[2]:= "- 12;
       CHLDECSOLBND(SYMBAND, 5, 1, AUX, RIGHT);
       "IF" AUX[3] = 5 "THEN"
       "BEGIN"
          OUTPUT(61, "("5(+2Z.4D2B), /"("DETERMINANT IS  ")" +.8D"+DD
          ")", RIGHT, CHLDETERMBND(SYMBAND, 5, 1))
       "END"
    "END"

    WHICH SOLVES THE SAME PROBLEM AS THE PROGRAM IN THE EXAMPLE  OF USE
    OF CHLSOLBND, DELIVERS:

     +1.0000   +1.0000   +1.0000   +1.0000   +1.0000
    DETERMINANT IS  +.60000000"+01
        "EOP"

SOURCE TEXT(S) :
"CODE" 34332;
"CODE" 34333;