NUMAL Section 3.1.2.1.1.1.2.3

BEGIN SECTION : 3.1.2.1.1.1.2.3 (June, 1974)

AUTHOR: W. HOFFMANN.

CONTRIBUTOR: J. C. P. BUS.

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED: 731210.

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS FOUR PROCEDURES
    FOR SOLVING A SYSTEM OF LINEAR EQUATIONS  WITH A
    TRIDIAGONAL MATRIX;
    SOLTRI CALCULATES A SOLUTION BY FORWARD AND BACK SUBSTITUTION IF
    THE TRIANGULAR DECOMPOSED FORM AS DELIVERED BY DECTRI IS GIVEN.
    DECSOLTRI  PERFORMS  THE TRIANGULAR DECOMPOSITION OF THE GIVEN
    MATRIX ( NOT USING ANY PIVOTING STRATEGY DURING THE PROCESS ) AND
    CALCULATES THE SOLUTION BY FORWARD AND BACK SUBSTITUTION.
    SOLTRIPIV CALCULATES A SOLUTION BY FORWARD AND BACK SUBTITUTION,IF
    THE TRIANGULAR DECOMPOSED FORM AS DELIVERED BY DECTRIPIV IS GIVEN.
    DECSOLTRIPIV PERFORMS THE TRIANGULAR DECOMPOSITION OF THE GIVEN
    MATRIX ( USING PARTIAL PIVOTING ) AND CALCULATES THE SOLUTION BY
    FORWARD AND BACK SUBSTITUTION.

KEYWORDS:

    ALGEBRAIC EQUATIONS,
    LINEAR SYSTEMS,
    TRIDIAGONAL MATRIX,
    FORWARD AND BACK SUBSTITUTION.


SUBSECTION: SOLTRI.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" SOLTRI(SUB, DIAG, SUPER, N, B);
    "VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, B;
    "CODE" 34424;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    SUB:    <ARRAY IDENTIFIER>;
            "ARRAY" SUB[1, N - 1];
            ENTRY  :  THE   SUBDIAGONAL  OF  THE
            LOWER-BIDIAGONAL MATRIX,  AS DELIVERED BY  DECTRI  (SECTION
            3.1.2.1.1.1.2.1);
    DIAG:   <ARRAY IDENTIFIER>;
            "ARRAY" DIAG[1:N];
            ENTRY :  THE DIAGONAL OF THE LOWER-
            BIDIAGONAL MATRIX, AS DELIVERED BY DECTRI;
    SUPER:  <ARRAY IDENTIFIER>;
            "ARRAY" SUPER[1: N - 1];
            ENTRY : THE SUPERDIAGONAL OF THE
            UPPER-BIDIAGONAL MATRIX AS DELIVERED BY DECTRI;
    N:      <ARITHMETICAL EXPRESSION>;
            THE ORDER OF THE MATRIX;
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            ENTRY:  THE RIGHT-HAND SIDE OF THE LINEAR SYSTEM;
            EXIT:   THE CALCULATED SOLUTION OF THE LINEAR SYSTEM.

PROCEDURES USED: NONE.

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    SOLTRI   CALCULATES   THE  SOLUTION  OF  A  LINEAR  SYSTEM  WITH  A
    TRIDIAGONAL  MATRIX,   WITH  FORWARD  AND  BACK  SUBSTITUTION;  THE
    TRIANGULARLY DECOMPOSED FORM OF THE MATRIX,  AS PRODUCED BY  DECTRI
    (SECTION  3.1.2.1.1.1.2.1),  SHOULD BE GIVEN;  ONE CALL  OF  DECTRI
    FOLLOWED BY SEVERAL CALLS OF  SOLTRI  MAY BE USED  TO SOLVE SEVERAL
    LINEAR SYSTEMS  HAVING  THE SAME TRIDIAGONAL MATRIX,  BUT DIFFERENT
    RIGHT-HAND SIDES.

EXAMPLE OF USE: SEE DECSOLTRI (THIS SECTION).


SUBSECTION: DECSOLTRI.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" DECSOLTRI(SUB, DIAG, SUPER, N, AUX, B);
    "VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, AUX, B;
    "CODE" 34425;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    SUB:    <ARRAY IDENTIFIER>;
            "ARRAY" SUB[1: N - 1];
            ENTRY:  THE  SUBDIAGONAL   OF  THE  GIVEN  MATRIX  T,  SAY;
                    T[I + 1, I]  SHOULD   BE  GIVEN  IN  SUB[I], I = 1,
                    ..., N - 1;
            EXIT:   SUPPOSE L DENOTES THE LOWER-BIDIAGONAL MATRIX, SUCH
                    THAT  LU = T,  FOR SOME UPPER-BIDIAGONAL MATRIX  U,
                    WITH UNIT DIAGONAL ELEMENTS, THEN L[I + 1, I]  WILL
                    BE DELIVERED IN SUB[I], I = 1, ..., AUX[3] - 1;
    DIAG:   <ARRAY IDENTIFIER>;
            "ARRAY" DIAG[1: N];
            ENTRY:  THE DIAGONAL OF T;
            EXIT:   L[I, I] WILL BE DELIVERED IN  DIAG[I],  I = 1, ...,
                    AUX[3];
    SUPER:  <ARRAY IDENTIFIER>;
            "ARRAY" SUPER[1: N - 1];
            ENTRY:  THE SUPERDIAGONAL OF T; T[I, I + 1] SHOULD BE GIVEN
                    IN SUPER[I], I = 1, ..., N - 1;
            EXIT:   U[I, I + 1]  WILL BE DELIVERED IN  SUPER[I], I = 1,
                    ..., AUX[3] - 1;
    N:      <ARITHMETICAL EXPRESSION>;
            THE ORDER OF THE MATRIX;
    AUX:    <ARRAY IDENTIFIER>;
            "ARRAY" AUX[2:5];
            ENTRY :
            AUX[2]: A RELATIVE TOLERANCE;  A REASONABLE CHOICE FOR THIS
                    VALUE IS AN ESTIMATE OF  THE RELATIVE PRECISION  OF
                    THE  MATRIX ELEMENTS,  HOWEVER, IT  SHOULD  NOT  BE
                    CHOSEN SMALLER THAN THE MACHINE PRECISION;
            EXIT :
            AUX[3]: THE NUMBER OF ELIMINATION STEPS PERFORMED;
            AUX[5]: IF AUX[3] = N, THEN AUX[5] WILL EQUAL THE INFINITY-
                    NORM OF THE MATRIX  (SEE  SECTION  3.1.2.1.1.1.2.1,
                    SUBSECTION DECTRI);
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            ENTRY:  THE RIGHT-HAND SIDE OF THE LINEAR SYSTEM;
            EXIT:   IF AUX[3] = N,  THEN  THE  SOLUTION  OF  THE LINEAR
                    SYSTEM  IS  OVERWRITTEN  ON  B,  ELSE   B   REMAINS
                    UNALTERED.

PROCEDURES USED:

    DECTRI = CP34423,
    SOLTRI = CP34424.

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    DECSOLTRI  CALCULATES  THE  SOLUTION  OF  A  LINEAR  SYSTEM  WITH A
    TRIDIAGONAL MATRIX; THE TRIANGULAR DECOMPOSITION IS DONE BY CALLING
    DECTRI    (SECTION  3.1.2.1.1.1.2.1)   AND  THE  FORWARD  AND  BACK
    SUBSTITUTION BY CALLING SOLTRI (THIS SECTION);  IF AUX[3] < N, THEN
    THE EFFECT OF DECSOLTRI IS MERELY THAT OF DECTRI.

EXAMPLE OF USE:

    LET  T  BE A TRIDIAGONAL MATRIX  WITH SUBDIAGONAL AND SUPERDIAGONAL
    ELEMENTS I * 2 AND I RESPECTIVELY (I = 1, ..., N - 1), AND DIAGONAL
    ELEMENTS I + 10 (I = 1, ..., N); LET  B  BE THE SECOND COLUMN OF T;
    THEN  THE SOLUTION  OF THE LINEAR SYSTEM   TX = B   IS GIVEN BY THE
    SECOND UNIT VECTOR;  BY THE FOLLOWING PROGRAM  WE  MAY  SOLVE  THIS
    SYSTEM AND PRINT THE ERROR IN THE CALCULATED SOLUTION.

    "BEGIN"
        "INTEGER" I;
        "ARRAY" D, SUB, SUPER, B[1:30], AUX[2:5];
        "FOR" I:= 1 "STEP" 1 "UNTIL" 30 "DO"
        "BEGIN" SUB[I]:= I * 2; SUPER[I]:= I; D[I]:= I + 10;
            B[I]:= 0
        "END"; B[1]:= 1; B[2]:= 12; B[3]:= 4;
        AUX[2]:= "-14;
        DECSOLTRI(SUB, D, SUPER, 30, AUX, B);
        OUTPUT(71, "("/,"("AUX[3] AND AUX[5]:")",2(/,N)")",
        AUX[3], AUX[5]);
        B[2]:= B[2] - 1;
        OUTPUT(71, "("//"("ERROR IN THE SOLUTION: ")", N")",
        SQRT(VECVEC(1, 30, 0, B, B)))
    "END"

    RESULTS:

    AUX[3] AND AUX[5]:
    +3.0000000000000"+001
    +1.2400000000000"+002

    ERROR IN THE SOLUTION: +0.0000000000000"+000


SUBSECTION: SOLTRIPIV.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" SOLTRIPIV(SUB, DIAG, SUPER, N, AID, PIV, B);
    "VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, AID, B;
    "BOOLEAN" "ARRAY" PIV;
    "CODE" 34427;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    SUB:    <ARRAY IDENTIFIER>;
            "ARRAY" SUB[1, N - 1];
            ENTRY : THE SUBDIAGONAL OF THE
            LOWER-BIDIAGONAL MATRIX, AS DELIVERED BY DECTRIPIV (SECTION
            3.1.2.1.1.1.2.1);
    DIAG:   <ARRAY IDENTIFIER>;
            "ARRAY" DIAG[1:N];
            ENTRY: THE DIAGONAL OF THE LOWER-
            BIDIAGONAL MATRIX, AS DELIVERED BY DECTRIPIV;
    SUPER:  <ARRAY IDENTIFIER>;
            "ARRAY" SUPER[1: N - 1];
            ENTRY : THE FIRST CODIAGONAL OF
            THE UPPER-TRIANGULAR MATRIX AS DELIVERED BY DECTRIPIV;
    N:      <ARITHMETICAL EXPRESSION>;
            THE ORDER OF THE MATRIX;
    AID:    <ARRAY IDENTIFIER>;
            "ARRAY" AID[1: N - 2];
            ENTRY:  THE SECOND CODIAGONAL OF
            THE UPPER-TRIANGULAR MATRIX AS DELIVERED BY DECTRIPIV;
    PIV:    <ARRAY IDENTIFIER>;
            "BOOLEAN""ARRAY" PIV[1: N-1];
            ENTRY:  THE PIVOT-
            INFORMATION AS DELIVERED BY DECTRIPIV;
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            ENTRY:  THE RIGHT-HAND SIDE OF THE LINEAR SYSTEM;
            EXIT:   THE CALCULATED SOLUTION OF THE LINEAR SYSTEM.

PROCEDURES USED: NONE.

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    SOLTRIPIV  CALCULATES  THE SOLUTION  OF  A  LINEAR  SYSTEM  WITH  A
    TRIDIAGONAL  MATRIX,   WITH  FORWARD  AND  BACK  SUBSTITUTION;  THE
    TRIANGULARLY DECOMPOSED FORM OF THE MATRIX,AS PRODUCED BY DECTRIPIV
    (SECTION 3.1.2.1.1.1.2.1), SHOULD BE GIVEN;  ONE CALL OF  DECTRIPIV
    FOLLOWED BY SEVERAL CALLS OF SOLTRIPIV MAY BE USED TO SOLVE SEVERAL
    LINEAR SYSTEMS  HAVING  THE SAME TRIDIAGONAL MATRIX,  BUT DIFFERENT
    RIGHT-HAND SIDES.

EXAMPLE OF USE:

    LET  T  BE THE MATRIX  AS GIVEN IN THE EXAMPLE OF USE OF  DECSOLTRI
    (THIS SECTION)  AND LET B1 AND B2 BE THE SECOND AND THIRD COLUMN OF
    T, THEN  THE SOLUTIONS OF THE LINEAR SYSTEMS  TX = B1  AND  TX = B2
    ARE GIVEN BY THE SECOND AND THIRD UNIT VECTOR  RESPECTIVELY; IN THE
    FOLLOWING PROGRAM  THESE SYSTEMS  ARE SOLVED  AND THE ERRORS IN THE
    CALCULATED SOLUTIONS ARE PRINTED.

    "BEGIN"
        "INTEGER" I;
        "ARRAY" D, SUB, SUPER, AID, B1, B2[1:30], AUX[2:5];
        "BOOLEAN" "ARRAY" PIV[1:29];
        "FOR" I:= 1 "STEP" 1 "UNTIL" 30 "DO"
        "BEGIN" SUB[I]:= I * 2; SUPER[I]:= I; D[I]:= I + 10;
            B1[I]:= B2[I]:= 0
        "END"; B1[1]:= 1; B1[2]:= 12; B1[3]:= 4;
        B2[2]:= 2; B2[3]:= 13; B2[4]:= 6;
        AUX[2]:= "-14;
        DECTRIPIV(SUB, D, SUPER, 30, AID, AUX, PIV);
        SOLTRIPIV(SUB, D, SUPER, 30, AID, PIV, B1);
        SOLTRIPIV(SUB, D, SUPER, 30, AID, PIV, B2);
        OUTPUT(71, "("/,"("AUX[3] AND AUX[5]:")",2(/,N)")",
        AUX[3], AUX[5]);
        B1[2]:= B1[2] - 1; B2[3]:= B2[3] - 1;
     OUTPUT(71, "("//"("ERROR IN B1: ")",N,/,"("ERROR IN B2: ")",N")",
        SQRT(VECVEC(1, 30, 0, B1, B1)), SQRT(VECVEC(1, 30, 0, B2, B2)))
    "END"

    RESULTS:

    AUX[3] AND AUX[5]:
    +3.0000000000000"+001
    +1.2400000000000"+002

    ERROR IN B1: +0.0000000000000"+000
    ERROR IN B2: +0.0000000000000"+000


SUBSECTION: DECSOLTRIPIV.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" DECSOLTRIPIV(SUB, DIAG, SUPER, N, AUX, B);
    "VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, AUX, B;
    "CODE" 34428;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    SUB:    <ARRAY IDENTIFIER>;
            "ARRAY" SUB[1: N - 1];
            ENTRY:  THE  SUBDIAGONAL   OF  THE  GIVEN  MATRIX  T,  SAY;
                    T[I + 1, I]  SHOULD   BE  GIVEN  IN  SUB[I], I = 1,
                    ..., N - 1;
            EXIT:   THE ELEMENTS OF SUB WILL BE OVERWRITTEN;
    DIAG:   <ARRAY IDENTIFIER>;
            "ARRAY" DIAG[1: N];
            ENTRY:  THE DIAGONAL OF T;
            EXIT:   THE ELEMENTS OF DIAG WILL BE OVERWRITTEN;
    SUPER:  <ARRAY IDENTIFIER>;
            "ARRAY" SUPER[1: N - 1];
            ENTRY:  THE SUPERDIAGONAL OF T; T[I, I + 1] SHOULD BE GIVEN
                    IN SUPER[I], I = 1, ..., N - 1;
            EXIT:   THE ELEMENTS OF SUPER WILL BE OVERWRITTEN;
    N:      <ARITHMETICAL EXPRESSION>;
            THE ORDER OF THE MATRIX;
    AUX:    <ARRAY IDENTIFIER>;
            "ARRAY" AUX[2:5];
            ENTRY:
            AUX[2]: A RELATIVE TOLERANCE;  A REASONABLE CHOICE FOR THIS
                    VALUE IS AN ESTIMATE OF  THE RELATIVE PRECISION  OF
                    THE  MATRIX ELEMENTS,  HOWEVER, IT  SHOULD  NOT  BE
                    CHOSEN SMALLER THAN THE MACHINE PRECISION;
            EXIT:
            AUX[3]: THE NUMBER OF ELIMINATION STEPS PERFORMED;
            AUX[5]: IF AUX[3] = N, THEN AUX[5] WILL EQUAL THE INFINITY-
                    NORM OF THE MATRIX  (SEE SECTION  3.1.2.1.1.1.2.1.,
                    SUBSECTION DECTRIPIV);
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1 : N];
            ENTRY:  THE RIGHT-HAND SIDE OF THE LINEAR SYSTEM;
            EXIT:   IF  AUX[3] = N,  THEN  THE SOLUTION  OF  THE LINEAR
                    SYSTEM WILL BE OVERWRITTEN ON B, ELSE B WILL REMAIN
                    UNALTERED.

PROCEDURES USED: NONE.

REQUIRED CENTRAL MEMORY:

    EXECUTION FIELD LENGTH: ONE  AUXILIARY ARRAY  OF  TYPE BOOLEAN  AND
                            ORDER N IS DECLARED IN DECSOLTRIPIV;

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    ONE CALL OF  DECSOLTRIPIV  IS EQUIVALENT WITH CALLING CONSECUTIVELY
    DECTRIPIV  (SECTION 3.1.2.1.1.1.2.1) AND  SOLTRIPIV (THIS SECTION);
    HOWEVER, DECSOLTRIPIV DOES NOT MAKE USE OF DECTRIPIV AND SOLTRIPIV,
    TO SAVE MEMORY SPACE AND TIME; THIS IS ONLY  TRUE  IN THE CASE THAT
    LINEAR SYSTEMS WITH  DIFFERENT MATRICES HAVE TO BE SOLVED; IF
    AUX[3] < N THEN
    DECSOLTRIPIV  IS TERMINATED PREMATURELY (SEE  DECTRIPIV  IN SECTION
    3.1.2.1.1.1.2.1).

EXAMPLE OF USE:

    THE SAME LINEAR SYSTEM AS GIVEN IN THE EXAMPLE OF USE OF  DECSOLTRI
    MAY BE SOLVED WITH DECSOLTRIPIV BY THE FOLLOWING PROGRAM:

    "BEGIN"
        "INTEGER" I;
        "ARRAY" D, SUB, SUPER, B[1:30], AUX[2:5];
        "FOR" I:= 1 "STEP" 1 "UNTIL" 30 "DO"
        "BEGIN" SUB[I]:= I * 2; SUPER[I]:= I; D[I]:= I + 10;
            B[I]:= 0
        "END"; B[1]:= 1; B[2]:= 12; B[3]:= 4;
        AUX[2]:= "-14;
        DECSOLTRIPIV(SUB, D, SUPER, 30, AUX, B);
        OUTPUT(71, "("/,"("AUX[3] AND AUX[5]:")",2(/,N)")",
        AUX[3], AUX[5]);
        B[2]:= B[2] - 1;
        OUTPUT(71, "("//"("ERROR IN THE SOLUTION: ")", N")",
        SQRT(VECVEC(1, 30, 0, B, B)))
    "END"

    RESULTS:

    AUX[3] AND AUX[5]:
    +3.0000000000000"+001
    +1.2400000000000"+002

    ERROR IN THE SOLUTION: +0.0000000000000"+000

SOURCE TEXTS:
"CODE" 34424;
"CODE" 34425;

"CODE" 34427;
"CODE" 34428;