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;