NUMAL Section 3.1.2.1.1.1.1.3

BEGIN SECTION : 3.1.2.1.1.1.1.3 (June, 1974)

AUTHOR         :    T.J. DEKKER.

REVISOR        :    J. KOK.

INSTITUTE      :    MATHEMATICAL CENTRE.

RECEIVED       :    730903.

BRIEF DESCRIPTION  :

    THIS SECTION CONTAINS TWO PROCEDURES.
    A) SOLBND, FOR THE SOLUTION OF ONE OR MORE SYSTEMS
    OF LINEAR EQUATIONS WITH THE SAME COEFFICIENT MATRIX, IF THIS
    MATRIX HAS BEEN DECOMPOSED BY A CALL OF THE PROCEDURE DECBND
    (SECTION 3.1.2.1.1.1.1.1.).
    B) DECSOLBND, FOR THE SOLUTION OF ONE SYSTEM OF
    LINEAR EQUATIONS BY GAUSSIAN ELIMINATION WITH STABILIZING ROW
    INTERCHANGES (PARTIAL PIVOTING) IF THE COEFFICIENT MATRIX IS IN
    BAND FORM AND IS STORED ROWWISE IN A ONE-DIMENSIONAL ARRAY.

KEY WORDS     :

    LINEAR EQUATIONS,
    PARTIAL PIVOTING,
    GAUSSIAN ELIMINATION,
    BAND MATRIX.


SUBSECTION     :    SOLBND.

CALLING SEQUENCE      :

    THE HEADING OF THE PROCEDURE IS    :

    "PROCEDURE" SOLBND(A, N, LW, RW, M, P, B); "VALUE" N, LW, RW;
    "INTEGER" N, LW, RW; "INTEGER""ARRAY" P; "ARRAY" A, M, B;
    "CODE" 34071;

    THE MEANING OF THE FORMAL PARAMETERS IS    :

        A, N, LW, RW, M, P :  SEE 'CALLING SEQUENCE' OF DECBND,
                ENTRY : THE CONTENTS OF THE ARRAYS A, M, P ARE AS
                PRODUCED BY DECBND;
        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,
    ELMVEC = CP34020.

RUNNING TIME   :
    (C3 * LW + C4 * RW + C5) * N;
    THE CONSTANTS C3, C4 AND C5 DEPEND UPON THE
    ARITHMETIC OF THE COMPUTER.

LANGUAGE       :    ALGOL 60.

METHOD AND PERFORMANCE :

    SOLBND CALCULATES THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS,
    PROVIDED THAT THE MATRIX WAS DECOMPOSED BY A SUCCESSFUL CALL OF
    DECBND (SECTION 3.1.2.1.1.1.1.1.).
    THE SOLUTION OF THE LINEAR SYSTEM IS OBTAINED BY CARRYING OUT THE
    ELIMINATIONS, FOR
    WHICH THE GAUSSIAN MULTIPLIERS ARE SAVED, ON THE RIGHT HAND SIDE,
    AND BY SOLVING THE NEW SYSTEM WITH THE UPPER TRIANGULAR BAND MATRIX
    , AS PRODUCED BY DECBND, BY BACK SUBSTITUTION. THE SOLUTIONS OF
    SEVERAL SYSTEMS WITH THE SAME COEFFICIENT MATRIX CAN BE OBTAINED BY
    SUCCESSIVE CALLS OF SOLBND.

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" 730822, TEST DECBND, SOLBND AND DETERMBND;
       "INTEGER" I; "INTEGER""ARRAY" ROWIND[1 : 5];
       "ARRAY" BAND[1 : 13], MULT[1 : 4], RIGHT, AUX[1 : 5];
       "FOR" I:= 1 "STEP" 1 "UNTIL" 13 "DO"
       BAND[I]:= "IF" (I + 1) // 3 * 3 < I "THEN" 2 "ELSE" - 1;
       RIGHT[1]:= RIGHT[5]:= 1;
       "FOR" I:= 2, 3, 4 "DO" RIGHT[I]:= 0; AUX[2]:= "- 12;
       DECBND(BAND, 5, 1, 1, AUX, MULT, ROWIND);
       "IF" AUX[3] = 5 "THEN"
       "BEGIN" SOLBND(BAND, 5, 1, 1, MULT, ROWIND, RIGHT);
          OUTPUT(61, "("5(+2Z.4D2B), /"("DETERMINANT IS  ")" +.8D"+DD
          ")", RIGHT, DETERMBND(BAND, 5, 1, 1, AUX[1]))
       "END"
    "END"

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


SUBSECTION      :    DECSOLBND.

CALLING SEQUENCE         :

    THE HEADING OF THE PROCEDURE IS    :

    "PROCEDURE" DECSOLBND(A, N, LW, RW, AUX, B); "VALUE" N, LW, RW;
    "INTEGER" N, LW, RW; "ARRAY" A, AUX, B;
    "CODE" 34322;

    THE MEANING OF THE FORMAL PARAMETERS IS    :

        A, N, LW, RW, AUX  : SEE DECBND (SECTION : 3.1.2.1.1.1.1.1);
        B                  : SEE SOLBND (THIS SECTION).

PROCEDURES USED    :

    VECVEC = CP34010,
    ELMVEC = CP34020,
    ICHVEC = CP34030.

REQUIRED CENTRAL MEMORY    :

    EXECUTION FIELD LENGTH :  A REAL ARRAY OF N ELEMENTS AND A REAL
    ARRAY OF LW + 1 ELEMENTS ARE DECLARED.

RUNNING TIME   :

    (C1 * LW + C6) * (LW + RW + 1) * N;
    THE CONSTANTS C1 AND C6 DEPEND UPON THE
    ARITHMETIC OF THE COMPUTER.

LANGUAGE       :    ALGOL 60.

METHOD AND PERFORMANCE :

    DECSOLBND PERFORMS GAUSSIAN ELIMINATION IN THE SAME WAY AS DECBND
    , MEANWHILE ALSO CARRYING OUT THE ELIMINATION WITH THE GIVEN
    RIGHT HAND SIDE. THE SOLUTION OF THE ELIMINATED SYSTEM IS OBTAINED
    BY BACK SUBSTITUTION.

EXAMPLE OF USE :

    THE PROGRAM

    "BEGIN""COMMENT" 730822, TEST DECSOLBND AND DETERMBND;
       "INTEGER" I;
       "ARRAY" BAND[1 : 13], RIGHT, AUX[1 : 5];

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

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

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

SOURCE TEXT(S) :
"CODE" 34071;

"CODE" 34322;