NUMAL Section 3.1.2.1.1.1.1.1

BEGIN SECTION : 3.1.2.1.1.1.1.1 (December, 1975)

AUTHOR         :    T.J. DEKKER.

REVISOR        :    J. KOK.

INSTITUTE      :    MATHEMATICAL CENTRE.

RECEIVED       :    730903.

BRIEF DESCRIPTION  :

    THIS SECTION CONTAINS THE PROCEDURE DECBND
    FOR THE DECOMPOSITION OF A BAND MATRIX BY GAUSSIAN ELIMINATION
    WITH STABILIZING ROW INTERCHANGES (PARTIAL PIVOTING).

KEY WORDS      :

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

CALLING SEQUENCE      :

    THE HEADING OF THE PROCEDURE IS    :

    "PROCEDURE" DECBND(A, N, LW, RW, AUX, M, P); "VALUE" N, LW, RW;
    "INTEGER" N, LW, RW; "INTEGER""ARRAY" P; "ARRAY" A, M, AUX;
    "CODE" 34320;

    THE MEANING OF THE FORMAL PARAMETERS IS    :

        A    :  <ARRAY IDENTIFIER>;
                "ARRAY" A[1 : (LW + RW) * (N - 1) + N];
                ENTRY  : A CONTAINS ROWWISE THE BAND ELEMENTS OF THE
                 BAND MATRIX IN SUCH A WAY THAT THE (I,J)-TH ELEMENT OF
                 THE MATRIX IS GIVEN IN A[( LW + RW ) * (I - 1) + J],
                 I=1,...,N AND J=MAX(1,I-LW),...,MIN(N,I+RW).
                 THE  VALUES  OF  THE  REMAINING  ELEMENTS  OF  A  ARE
                 IRRELEVANT.
                EXIT   : THE BAND ELEMENTS OF THE GAUSSIAN ELIMINATED
                 MATRIX, WHICH IS AN UPPERTRIANGULAR BAND MATRIX WITH
                 (LW + RW) CODIAGONALS, ARE ROWWISE DELIVERED IN A  AS
                 FOLLOWS: THE (I,J)-TH ELEMENT OF U IS
                 A [ ( LW + RW ) * (I - J) + J ],I=1,...,N AND
                 J=I,...,MIN(N,I + LW + RW).
        N    :  <ARITHMETIC EXPRESSION>;
                ORDER OF THE BAND MATRIX;
        LW   :  <ARITHMETIC EXPRESSION>;
                NUMBER OF  LEFT CODIAGONALS OF A;

        RW   :  <ARITHMETIC EXPRESSION>;
                NUMBER OF RIGHT CODIAGONALS OF A;
        AUX  :  <ARRAY IDENTIFIER>;
                "ARRAY" AUX[1 : 5];
                ENTRY  :AUX[2] = EPS IS A RELATIVE TOLERANCE TO CONTROL
                  THE ELIMINATION; THE PROCESS IS DISCONTINUED IF
                  (EPS > PIVOT[I] / EUCLIDEAN NORM OF I-TH ROW)
                  IN THE I-TH ELIMINATION STEP;
                NORMAL EXIT  :
                  AUX[1] = SIGN OF THE DETERMINANT OF THE MATRIX
                  (+1 OR -1);
                  AUX[3] = N;
                  AUX[5] = MINIMUM ABSOLUTE VALUE OF
                  PIVOT[I] / EUCLIDEAN NORM OF THE I-TH ROW;
                ABNORMAL EXIT : IF THE ELIMINATION CANNOT BE CARRIED
                  OUT, I.E. IF TEMP (THE QUANTITY
                  ABS(PIVOT[I] / EUCLIDEAN NORM OF THE I-TH ROW))
                  IS TOO SMALL IN THE I-TH ELIMINATION STEP :
                  AUX[3] = I - 1,
                  AUX[5] = TEMP;
        M  :    <ARRAY IDENTIFIER>;
                "ARRAY" M[1 : LW * (N - 2) + 1];
                EXIT :  THE GAUSSIAN MULTIPLIERS OF ALL ELIMINATIONS
                 IN SUCH A WAY THAT THE I-TH MULTIPLIER OF THE J-TH
                 STEP  IS  M [ LW * (J - 1) + I - J ].
        P  :    <ARRAY IDENTIFIER>;
                "INTEGER""ARRAY" P[1 : N];
                EXIT :  THE PIVOTAL INDICES.

PROCEDURES USED    :

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

REQUIRED CENTRAL MEMORY    :

    EXECUTION FIELD LENGTH  : A REAL ARRAY OF N ELEMENTS IS DECLARED.

RUNNING TIME   :

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

LANGUAGE       :    ALGOL 60.

METHOD AND PERFORMANCE :

    DECBND PERFORMS THE DECOMPOSITION OF A MATRIX WHOSE NON-ZERO
    ELEMENTS ARE IN BAND FORM, AND WHOSE BAND ELEMENTS ARE STORED
    ROWWISE IN A ONE-DIMENSIONAL ARRAY.
    THE METHOD USED IS GAUSSIAN ELIMINATION WITH STABILIZING ROW
    INTERCHANGES (PARTIAL PIVOTING).
    THE GAUSSIAN ELIMINATION IS PERFORMED IN N STEPS. IN THE K-TH
    STEP, K = 1, ... , N, A PIVOT IS SELECTED IN THE K-TH COLUMN OF
    THE REMAINING SUBMATRIX OF ORDER N - K + 1 (THIS COLUMN
    CONTAINS AT MOST LW + 1 NON-ZERO ELEMENTS); THEN THE PIVOTAL
    ROW IS INTERCHANGED WITH THE K-TH ROW; SUBSEQUENTLY THE K-TH
    UNKNOWN IS ELIMINATED IN THE LAST N - K ROWS (ONLY THE FIRST
    LW OF THESE LAST ROWS ARE INVOLVED HERE).
    THE PIVOT IS SELECTED IN SUCH A WAY THAT ITS ABSOLUTE
    VALUE DIVIDED BY THE EUCLIDEAN NORM OF THE CORRESPONDING ROW OF
    THE MATRIX IS MAXIMAL. THUS, THE MATRIX IS EQUILIBRATED IN THIS
    PIVOTING STRATEGY SUCH, THAT THE ROWS EFFECTIVELY OBTAIN UNIT
    EUCLIDEAN NORM.
    THE PROCEDURE DELIVERS THE BAND ELEMENTS OF THE ELIMINATED MATRIX
    (WHICH IS AN UPPER TRIANGULAR MATRIX WITH LW + RW
    SUPERDIAGONALS) AND THE GAUSSIAN MULTIPLIERS FOR EACH ELIMINATION
    .
    THE ELIMINATION CANNOT BE CARRIED OUT IF THE ABSOLUTE VALUE OF THE
    PIVOT IS LESS THAN A GIVEN RELATIVE TOLERANCE (AUX[2]) TIMES THE
    EUCLIDEAN NORM OF THE CORRESPONDING ROW OF THE MATRIX. THEN THE
    PREVIOUS STEP NUMBER OF THE ELIMINATION IS DELIVERED (IN AUX[3],
    WHICH ELSE TAKES THE VALUE N).  SEE ALSO REF [1], SECTION 212.

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 SOLBND.

SOURCE TEXT(S) :
"CODE" 34320;