NUMAL Section 3.1.2.1.1.2.2.1

BEGIN SECTION : 3.1.2.1.1.2.2.1 (June, 1974)

AUTHOR: W. HOFFMANN.

CONTRIBUTOR: J. C. P. BUS.

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED: 731215.

BRIEF DESCRIPTION:
    THIS  SECTION  CONTAINS  A  PROCEDURE,  DECSYMTRI,   TO  PERFORM  A
    TRIANGULAR DECOMPOSITION OF A SYMMETRIC TRIDIAGONAL MATRIX.

KEYWORDS:

    LU DECOMPOSITION,
    TRIANGULAR DECOMPOSITION,
    SYMMETRIC TRIDIAGONAL MATRIX.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" DECSYMTRI(DIAG, CO, N, AUX);
    "VALUE" N; "INTEGER" N; "ARRAY" DIAG, CO, AUX;
    "CODE" 34420;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    DIAG:   <ARRAY IDENTIFIER>;
            "ARRAY" DIAG[1: N];
            ENTRY:  THE DIAGONAL OF THE GIVEN MATRIX T, SAY;
            EXIT:   SUPPOSE U DENOTES THE UNIT UPPER-BIDIAGONAL MATRIX,
                    SUCH THAT  U'DU = T   FOR SOME  DIAGONAL MATRIX  D,
                    WHERE U' DENOTES THE TRANSPOSED MATRIX; THEN D[I,I]
                    WILL BE DELIVERED IN DIAG[I], I = 1, ..., AUX[3];
    CO:     <ARRAY IDENTIFIER>;
            "ARRAY" CO[1: N - 1];
            ENTRY:  THE CODIAGONAL OF T; T[I, I + 1] SHOULD BE GIVEN IN
                    CO[I], I = 1, ..., N - 1;
            EXIT:   U[I, I + 1] WILL BE DELIVERED IN CO[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,  ELSE  AUX[5]  IS SET  EQUAL TO
                    THE  VALUE  OF  THAT  ELEMENT   WHICH   CAUSES  THE
                    BREAKDOWN OF THE DECOMPOSITION.

PROCEDURES USED: NONE.

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    THE METHOD USED IN DECSYMTRI  YIELDS A UNIT UPPER-BIDIAGONAL MATRIX
    U AND A DIAGONAL MATRIX  D, SUCH THAT THE PRODUCT  U'DU  EQUALS THE
    GIVEN  SYMMETRIC TRIDIAGONAL MATRIX;  THE PROCESS  IS TERMINATED IN
    THE K-TH STEP  IF  THE MODULUS  OF  THE  K-TH  DIAGONAL ELEMENT  IS
    SMALLER THAN  A CERTAIN  SMALL  VALUE,  WHICH  IS GIVEN  BY  AUX[2]
    MULTIPLIED BY THE 1-NORM OF THE K-TH ROW;  IN THIS CASE AUX[3] WILL
    BE GIVEN THE VALUE  K - 1  AND  AUX[5]  WILL BE GIVEN  THE VALUE OF
    THE K-TH DIAGONAL ELEMENT.

EXAMPLE OF USE: SEE DECSOLSYMTRI (SECTION 3.1.2.1.1.2.2.3).

SOURCE TEXT:
"CODE" 34420;