NUMAL Section 3.2.1.2.2.2

BEGIN SECTION : 3.2.1.2.2.2 (June, 1974)

AUTHOR   : C.G. VAN DER LAAN.

CONTRIBUTORS : H.FIOLET, C.G. VAN DER LAAN.

INSTITUTE : MATHEMATICAL CENTRE.

RECEIVED: 731016.

BRIEF DESCRIPTION :

    THIS SECTION CONTAINS THE PROCEDURES HSHCOMHES AND BAKCOMHES.
    HSHCOMHES TRANSFORMS A COMPLEX MATRIX BY MEANS OF HOUSEHOLDER'S
    TRANSFORMATION FOLLOWED BY A COMPLEX DIAGONAL TRANSFORMATION INTO
    A SIMILAR UNITARY UPPER-HESSENBERG MATRIX WITH A REAL NONNEGATIVE
    SUBDIAGONAL.
    BAKCOMHES PERFORMS THE CORRESPONDING BACK TRANSFORMATION.

KEYWORDS:

    COMPLEX EIGENPROBLEM,
    REDUCTION HESSENBERG FORM,
    HOUSEHOLDER'S TRANSFORMATION.


SUBSECTION: HSHCOMHES.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE" HSHCOMHES(AR, AI, N, EM, B, TR, TI, DEL); "VALUE" N;
    "INTEGER" N; "ARRAY" AR, AI, EM, B, TR, TI, DEL;
    "CODE" 34366;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    AR,AI:     <ARRAY IDENTIFIER>;
               "ARRAY" AR,AI[1:N,1:N];
               ENTRY:
               THE REAL PART AND THE IMAGINARY PART OF THE MATRIX TO BE
               TRANSFORMED  MUST BE GIVEN IN THE ARRAYS AR AND AI,
               RESPECTIVELY;
               EXIT:
               THE REAL PART AND THE IMAGINARY PART OF THE UPPER
               TRIANGLE OF THE RESULTING UPPER-HESSENBERG MATRIX ARE
               DELIVERED IN THE CORRESPONDING PARTS OF THE ARRAYS AR
               AND AI, RESPECTIVELY; DATA FOR THE HOUSEHOLDER BACK-
               TRANSFORMATION ARE DELIVERED IN THE STRICT LOWER
               TRIANGLES OF THE ARRAYS AR AND AI;

    N:         <ARITHMETIC EXPRESSION>;
               THE ORDER OF THE GIVEN MATRIX;
    EM:        <ARRAY IDENTIFIER>;
               "ARRAY"EM[0:1];
               ENTRY:
               EM[0]: THE MACHINE PRECISION;
               EM[1]: AN ESTIMATE OF THE NORM OF THE COMPLEX MATRIX;
                 (OR, E.G. THE SUM OF THE INFINITY NORMS OF THE REAL
                 (PART AND IMAGINARY PART OF THE MATRIX);
    B:         <ARRAY IDENTIFIER>;
               "ARRAY"B[1:N-1];
               EXIT:
               THE REAL NONNEGATIVE SUBDIAGONAL OF THE RESULTING
               UPPER-HESSENBERG MATRIX;
    TR,TI:     <ARRAY IDENTIFIER>;
               "ARRAY" TR,TI[1:N];
               EXIT:
               THE REAL PART AND THE IMAGINARY PART OF THE DIAGONAL
               ELEMENTS OF A DIAGONAL SIMILARITY TRANSFORMATION ARE
               DELIVERED IN THE ARRAYS TR AND TI, RESPECTIVELY; BY THIS
               INFORMATION THE COMPLEX UPPER-HESSENBERG MATRIX IS
               TRANSFORMED INTO A UPPER-HESSENBERG MATRIX WITH A REAL
               SUBDIAGONAL;
    DEL:       <ARRAY IDENTIFIER>;
               "ARRAY"DEL[1:N-2];
               EXIT:
               INFORMATION CONCERNING THE SEQUENCE OF HOUSEHOLDER
               MATRICES.

PROCEDURES USED:

    HSHCOMCOL = CP34355,
    MATMAT    = CP34013,
    ELMROWCOL = CP34028,
    HSHCOMPRD = CP34356,
    CARPOL    = CP34344,
    COMMUL    = CP34341,
    COMCOLCST = CP34352,
    COMROWCST = CP34353.

RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE: SEE BAKCOMHES (THIS SECTION).


SUBSECTION: BAKCOMHES.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE" BAKCOMHES(AR, AI, TR, TI, DEL, VR, VI, N, N1, N2);
    "VALUE" N, N1, N2; "INTEGER" N, N1, N2;
     "ARRAY" AR, AI, TR, TI, DEL, VR, VI;
    "CODE" 34367;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    AR,AI,TR,TI,DEL:
               <ARRAY IDENTIFIER>;
               "ARRAY" AR,AI[1:N,1:N];
               "ARRAY" TR,TI[1:N];
               "ARRAY"DEL[1:N-2];
               ENTRY: THE DATA FOR THE BACKTRANSFORMATION AS PRODUCED
                      BY HSHCOMHES;
    VR,VI:     <ARRAY IDENTIFIER>;
               "ARRAY" VR,VI[1:N,N1:N2];
               ENTRY:
               THE BACK TRANSFORMATION IS PERFORMED ON THE EIGENVECTORS
               WITH THE REAL PARTS GIVEN IN ARRAY VR AND THE IMAGINARY
               PARTS GIVEN IN ARRAY VI;
               EXIT:
               THE REAL PARTS AND IMAGINARY PARTS OF THE RESULTING
               EIGENVECTORS ARE DELIVERED IN THE COLUMNS OF THE ARRAYS
               VR AND VI, RESPECTIVELY;
    N:         <ARITHMETIC EXPRESSION>;
               THE ORDER OF THE MATRIX OF WHICH THE EIGENVECTORS ARE
               CALCULATED;
    N1,N2:     <ARITHMETIC EXPRESSION>;
               THE EIGENVECTORS CORRESPONDING TO THE EIGENVALUES WITH
               INDICES N1,...,N2 ARE TO BE TRANSFORMED;

PROCEDURES USED:

    COMROWCST = CP34353,
    HSHCOMPRD = CP34356.

RUNNING TIME: PROPORTIONAL TO (N2-N1) * N**2.

LANGUAGE : ALGOL 60.

THE FOLLOWING HOLDS FOR BOTH PROCEDURES:

METHOD AND PERFORMANCE:

    HSHCOMHES:
    HOUSEHOLDER'S TRANSFORMATION (FOR COMPLEX MATRICES) IS A UNITARY
    SIMILARITY TRANSFORMATION, WHICH TRANSFORMS A COMPLEX MATRIX INTO A
    SIMILAR UPPER-HESSENBERG MATRIX (SEE WILKINSON, 1965, P. 347-349).
    LET M BE A GIVEN COMPLEX MATRIX OF ORDER N, P THE TRANSFORMING
    MATRIX AND H THE RESULTING UPPER-HESSENBERG MATRIX. SINCE P IS
    UNITARY, WE THEN HAVE H = P''MP, WHERE '' STANDS FOR CONJUGATING
    AND TRANSPOSING.  THE MATRIX P IS  THE PRODUCT OF  N-2 HOUSEHOLDER
    MATRICES,  THESE  BEING  UNITARY  HERMITEAN  MATRICES  OF
    THE FORM I - UU''/T, WHERE T IS A SCALAR (>0), AND U A COMPLEX
    VECTOR. THE R-TH HOUSEHOLDER MATRIX, R=1,...,N-2, IS CHOSEN IN SUCH
    A WAY THAT THE FIRST R ELEMENTS OF U VANISH, AND THE DESIRED ZEROS
    ARE INTRODUCED IN THE LAST N-R-1 ELEMENTS OF THE R-TH COLUMN OF THE
    MATRIX M. HOWEVER, IF THE EUCLIDEAN NORM OF THE LAST N-R-1 ELEMENTS
    OF COLUMN R OF THE MATRIX M IS SMALLER THAN THE MACHINE PRECISION
    TIMES A NORM OF THE MATRIX THEN THE R-TH TRANSFORMATION IS SKIPPED
    (I.E. THE R-TH HOUSEHOLDER MATRIX IS REPLACED BY I). THE COMPLEX
    DIAGONAL SIMILARITY TRANSFORMATION D TRANSFORMS THE UPPER-
    HESSENBERG MATRIX H INTO AN UPPER-HESSENBERG MATRIX HR, WITH REAL
    NONNEGATIVE ELEMENTS. THE DIAGONAL OF D IS CHOSEN IN SUCH A WAY
    THAT SUBDIAGONAL ELEMENTS OF H ARE TRANSFORMED INTO THEIR ABSOLUTE
    VALUES (SEE MUELLER, 1966).
    BAKCOMHES:
    THE BACK TRANSFORMATION TRANSFORMS A COMPLEX VECTOR X INTO THE
    COMPLEX VECTOR PDX. IF X IS AN EIGENVECTOR OF H  THEN PDX IS THE
    CORRESPONDING EIGENVECTOR OF M. STARTING FROM THE VECTOR V=DX, THE
    VECTOR PDX IS OBTAINED BY SUCCESSIVELY REPLACING V BY THE R-TH
    HOUSEHOLDER MATRIX TIMES V, FOR R=N-2,...,1. THE RESULTING VECTOR
    THEN EQUALS PDX.

REFERENCES:

    MUELLER, D.J. (1966),
    HOUSEHOLDER'S METHOD  FOR  COMPLEX MATRICES AND EIGENSYSTEMS   OF
    HERMITIAN MATRICES,
    NUMER.MATH., 8, P.72-92;

    WILKINSON, J.H. (1965),
    THE ALGEBRAIC EIGENVALUE PROBLEM,
    CLARENDON PRESS, OXFORD;

EXAMPLE OF USE:

    HSHCOMHES IS USED IN THE PROCEDURES EIGVALCOM AND EIGCOM.
    BAKCOMHES IS USED IN THE PROCEDURE EIGCOM.
    (SEE SECTION 3.3.2.2.2.).

SOURCE TEXT(S) :
"CODE" 34366;
"CODE" 34367;