NUMAL Section 3.2.1.2.1.1

BEGIN SECTION : 3.2.1.2.1.1 (December, 1979)

AUTHORS:      T.J.DEKKER, W.HOFFMANN.

CONTRIBUTORS: W.HOFFMANN, J.G.VERWER.

INSTITUTE:    MATHEMATICAL CENTRE.

RECEIVED:     730705.

BRIEF DESCRIPTION:
    THIS SECTION CONTAINS FIVE PROCEDURES.
    A) TFMSYMTRI2 AND TFMSYMTRI1 TRANSFORM A REAL SYMMETRIC MATRIX INTO
    A SIMILAR TRIDIAGONAL ONE BY MEANS OF HOUSEHOLDER'S TRANSFORMATION,
    B) BAKSYMTRI2   AND   BAKSYMTRI1  PERFORM  THE  CORRESPONDING  BACK
    TRANSFORMATION  AND  FINALLY,
    C) TFMPREVEC (WHICH IS TO BE USED IN COMBINATION  WITH  TFMSYMTRI2)
    CALCULATES THE TRANSFORMING MATRIX.
    TFMSYMTRI2  AND  BAKSYMTRI2  USE  THE  UPPER  TRIANGLE  OF  A  TWO-
    DIMENSIONAL  ARRAY  FOR THE UPPER  TRIANGLE OF THE GIVEN  SYMMETRIC
    MATRIX  (TFMSYMTRI2)  OR  FOR  THE  DATA  FOR   HOUSEHOLDER'S  BACK
    TRANSFORMATION  (BAKSYMTRI2).  THE OTHER  ELEMENTS ARE NEITHER USED
    NOR CHANGED.  TFMSYMTRI1 AND
                  BAKSYMTRI1 USE AN ARRAY A[1:(N+1)*N//2] FOR THE GIVEN
    SYMMETRIC  MATRIX (TFMSYMTRI1)  OR  FOR THE DATA FOR  HOUSEHOLDER'S
    TRANSFORMATION (BAKSYMTRI1).

KEYWORDS:
    HOUSEHOLDER'S TRANSFORMATION,
    TRIANGULARIZATION.


SUBSECTION: TFMSYMTRI2.

CALLING SEQUENCE:
    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" TFMSYMTRI2(A, N, D, B, BB, EM); "VALUE" N;
    "INTEGER" N; "ARRAY" A, D, B, BB, EM; "CODE" 34140;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE GIVEN MATRIX;
    A:      <ARRAY IDENTIFIER>;
            "ARRAY"A[1:N,1:N];
            ENTRY:  THE UPPER TRIANGLE OF THE SYMMETRIC MATRIX  MUST BE
                    GIVEN  IN  THE  UPPER  TRIANGULAR  PART  OF  A (THE
                    ELEMENTS A[I,J],I<=J);
            EXIT:   THE DATA FOR HOUSEHOLDER'S  BACK  TRANSFORMATION IS
                    DELIVERED IN THE  UPPER  TRIANGULAR  PART OF A. THE
                    ELEMENTS  A[I,J], I>J ARE NEITHER USED NOR CHANGED;
    D:      <ARRAY IDENTIFIER>;
            "ARRAY"D[1:N];
            EXIT:   THE  MAIN  DIAGONAL  OF THE  SYMMETRIC  TRIDIAGONAL
                    MATRIX   T  (SAY),   PRODUCED   BY  HOUSEHOLDER'S
                    TRANSFORMATION;
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            EXIT:   THE CODIAGONAL  ELEMENTS OF T ARE DELIVERED IN B[1]
                    THROUGH B[N-1]; B[N] IS SET EQUAL TO ZERO;
    BB:     <ARRAY IDENTIFIER>;
            "ARRAY"BB[1:N];
            EXIT:   THE  SQUARES  OF THE  CODIAGONAL  ELEMENTS OF T ARE
                    DELIVERED  IN  BB[1] THROUGH BB[N-1];  BB[N] IS SET
                    EQUAL TO ZERO;
    EM:     <ARRAY IDENTIFIER>;
            "ARRAY"EM[0:1];
            ENTRY:  EM[0], THE MACHINE PRECISION;
            EXIT:   EM[1], THE  INFINITY  NORM OF THE ORIGINAL  MATRIX.

PROCEDURES USED:
    TAMVEC   =      CP34012,
    MATMAT   =      CP34013,
    TAMMAT   =      CP34014,
    ELMVECCOL=      CP34021,
    ELMCOLVEC=      CP34022,
    ELMCOL   =      CP34023.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.

METHOD AND PERFORMANCE:
    A  GIVEN  SYMMETRIC  MATRIX M IS TRANSFORMED INTO A TRIDIAGONAL ONE
    BY  MEANS OF N-1 ORTHOGONAL  SIMILARITY  TRANSFORMATIONS; THE  P-TH
    TRANSFORMATION  IS  CHOSEN  IN  SUCH  A  WAY THAT IN THE (N-P+1)-TH
    COLUMN AND ROW OF M THE DESIRED  ZEROES  ARE  INTRODUCED.  HOWEVER,
    IF, IN THIS COLUMN AND ROW, ALL ELEMENTS OUTSIDE THE MAIN  DIAGONAL
    AND THE  ADJACENT  CODIAGONALS  ARE SMALLER IN ABSOLUTE  VALUE THAN
    THE INFINITY NORM OF M TIMES THE MACHINE  PRECISION, THEN THE  P-TH
    TRANSFORMATION IS SKIPPED.
    FOR FURTHER DETAILS SEE REF[1] AND REF[2].


SUBSECTION: BAKSYMTRI2.

CALLING SEQUENCE:
    THE HEADING OF THE PROCEDURE IS:
    "PROCEDURE" BAKSYMTRI2(A, N, N1, N2, VEC); "VALUE" N, N1, N2;
    "INTEGER" N, N1, N2; "ARRAY" A, VEC; "CODE" 34141;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:      <ARRAY IDENTIFIER>;
            "ARRAY"A[1:N,1:N];
            ENTRY:  THE DATA FOR THE BACK  TRANSFORMATION,  AS PRODUCED
                    BY  TFMSYMTRI2,   MUST   BE   GIVEN  IN  THE  UPPER
                    TRIANGULAR PART OF A;
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE GIVEN MATRIX;
    N1,N2:  <ARITHMETIC EXPRESSION>;
            LOWER AND UPPER BOUND, RESPECTIVELY, OF THE COLUMN NUMBERS
            OF VEC;
    VEC:    <ARRAY IDENTIFIER>;
            "ARRAY"VEC[1:N,N1:N2];
            ENTRY:  THE VECTORS ON WHICH THE BACK TRANSFORMATION HAS TO
                    BE PERFORMED;
            EXIT:   THE TRANSFORMED VECTORS.

PROCEDURES USED:
    TAMMAT  =       CP34014,
    ELMCOL  =       CP34023.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N SQUARED TIMES (N2-N1+1).

METHOD AND PERFORMANCE: SEE REF[1].


SUBSECTION: TFMPREVEC.

CALLING SEQUENCE:
    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" TFMPREVEC(A, N); "VALUE" N; "INTEGER" N; "ARRAY" A;
    "CODE" 34142;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:      <ARRAY IDENTIFIER>;
            "ARRAY"A[1:N,1:N];
            ENTRY:  THE DATA  FOR THE BACK  TRANSFORMATION, AS PRODUCED
                    BY   TFMSYMTRI2,   MUST   BE  GIVEN  IN  THE  UPPER
                    TRIANGULAR PART OF A;
            EXIT:   THE MATRIX  WHICH  TRANSFORMS  THE ORIGINAL  MATRIX
                    INTO A SIMILAR TRIDIAGONAL ONE.
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE MATRIX;

PROCEDURES USED:
    TAMMAT  =       CP34014,
    ELMCOL  =       CP34023.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.

METHOD AND PERFORMANCE: SEE REF[1].


SUBSECTION: TFMSYMTRI1.

CALLING SEQUENCE:
    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" TFMSYMTRI1(A, N, D, B, BB, EM); "VALUE" N;
    "INTEGER" N; "ARRAY" A, D, B, BB, EM; "CODE" 34143;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:      <ARRAY IDENTIFIER>;
            "ARRAY"A[1:(N+1)*N//2];
            ENTRY:  THE  UPPER  TRIANGLE OF THE GIVEN  MATRIX  MUST  BE
                    GIVEN  IN SUCH A WAY THAT THE  (I,J)-TH  ELEMENT OF
                    THE MATRIX IS A[(J-1)*J//2+I], 1<=I<=J<=N;
            EXIT:   THE DATA FOR HOUSEHOLDER'S BACK TRANSFORMATION AS
                    USED BY BAKSYMTRI1;
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE GIVEN MATRIX;
    D:      <ARRAY IDENTIFIER>;
            "ARRAY"D[1:N];
            EXIT:   THE  MAIN  DIAGONAL  OF THE  SYMMETRIC  TRIDIAGONAL
                    MATRIX   T  (SAY),   PRODUCED   BY  HOUSEHOLDER'S
                    TRANSFORMATION;
    B:      <ARRAY IDENTIFIER>;
            "ARRAY" B[1:N];
            EXIT:   THE CODIAGONAL  ELEMENTS OF T ARE DELIVERED IN B[1]
                    THROUGH B[N-1]; B[N] IS SET EQUAL TO ZERO;
    BB:     <ARRAY IDENTIFIER>;
            "ARRAY"BB[1:N];
            EXIT:   THE  SQUARES  OF THE  CODIAGONAL  ELEMENTS OF T ARE
                    DELIVERED  IN  BB[1] THROUGH BB[N-1];  BB[N] IS SET
                    EQUAL TO ZERO;
    EM:     <ARRAY IDENTIFIER>;
            "ARRAY"EM[0:1];
            ENTRY:  EM[0], THE MACHINE PRECISION;
            EXIT:   EM[1], THE  INFINITY  NORM OF THE  ORIGINAL MATRIX.

PROCEDURES USED:
    VECVEC  =       CP34010,
    SEQVEC  =       CP34016,
    ELMVEC  =       CP34020.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.

METHOD AND PERFORMANCE: SEE TFMSYMTRI2 (THIS SECTION).


SUBSECTION: BAKSYMTRI1.

CALLING SEQUENCE:
    THE HEADING OF THE PROCEDURE IS:
    "PROCEDURE" BAKSYMTRI1(A, N, N1, N2, VEC); "VALUE" N, N1, N2;
    "INTEGER" N, N1, N2; "ARRAY" A, VEC; "CODE" 34144;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:      <ARRAY IDENTIFIER>;
            "ARRAY"A[1:(N+1)*N//2];
            ENTRY:  THE DATA FOR THE BACK  TRANSFORMATION, AS  PRODUCED
                    BY  TFMSYMTRI1;
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE GIVEN MATRIX;
    N1,N2:  <ARITHMETIC EXPRESSION>;
            LOWER AND UPPER BOUND, RESPECTIVELY, OF THE COLUMN NUMBERS
            OF VEC;
    VEC:    <ARRAY IDENTIFIER>;
            "ARRAY"VEC[1:N,N1:N2];
            ENTRY:  THE VECTORS ON WHICH THE BACK TRANSFORMATION HAS TO
                    BE PERFORMED;
            EXIT:   THE TRANSFORMED VECTORS.

PROCEDURES USED:
    VECVEC  =       CP34010,
    ELMVEC  =       CP34020.

REQUIRED CENTRAL MEMORY:
    AN AUXILIARY  ONE-DIMENSIONAL REAL ARRAY OF LENGTH N IS USED.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N SQUARED TIMES (N2-N1+1).

METHOD AND PERFORMANCE: SEE REF[1].

REFERENCES:
    [1]     DEKKER, T.J. AND HOFFMANN, W.
            ALGOL 60 PROCEDURES IN NUMERICAL ALGEBRA, PART 2,
            MATHEMATICAL CENTRE TRACTS 23,
            MATHEMATISCH CENTRUM, AMSTERDAM, 1968;

    [2]     WILKINSON, J.H.
            THE ALGEBRAIC EIGENVALUE PROBLEM,
            CLARENDON PRESS, OXFORD 1965.

EXAMPLE OF USE:

    THE   FIVE   PROCEDURES  OF  THIS   SECTION  ARE  USED  IN
    SECTION 3.3.1.1.2:
            EIGSYM2 USES TFMSYMTRI2 AND BAKSYMTRI2;
            EIGSYM1 USES TFMSYMTRI1 AND BAKSYMTRI1;
            QRISYM  USES TFMSYMTRI2 AND TFMPREVEC.

SOURCE TEXT(S):
"CODE" 34140;
"CODE" 34141;

"CODE" 34142;
"CODE" 34143;
"CODE" 34144;