NUMAL Section 3.2.1.2.2.1
BEGIN SECTION : 3.2.1.2.2.1 (June, 1974)
AUTHOR : C.G. VAN DER LAAN.
CONTRIBUTORS : H.FIOLET, C.G. VAN DER LAAN.
INSTITUTE : MATHEMATICAL CENTRE.
RECEIVED : 730903.
BRIEF DESCRIPTION :
THIS SECTION CONTAINS THREE PROCEDURES;
A) HSHHRMTRI TRANSFORMS THE HERMITIAN MATRIX M INTO A SIMILAR
REAL SYMMETRIC TRIDIAGONAL MATRIX S;
B) BAKHRMTRI PERFORMS A BACK TRANSFORMATION CORRESPONDING TO
HSHHRMTRI;
C) HSHHRMTRIVAL DELIVERS THE MAIN DIAGONAL ELEMENTS AND THE
SQUARES OF THE CODIAGONAL ELEMENTS OF A HERMITIAN TRIDIAGONAL
MATRIX WHICH IS UNITARY SIMILAR WITH A GIVEN HERMITIAN MATRIX.
KEYWORDS :
HERMITIAN MATRIX ,
TRIDIAGONALIZATION ,
COMPLEX HOUSEHOLDER,S TRANSFORMATION .
SUBSECTION : HSHHRMTRI.
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE READS :
"PROCEDURE" HSHHRMTRI(A, N, D, B, BB, EM, TR, TI); "VALUE" N;
"INTEGER" N; "ARRAY" A, D, B, BB, EM, TR, TI;
"CODE" 34363;
THE MEANING OF THE FORMAL PARAMETERS IS :
A,TR,TI: <ARRAY IDENTIFIER>;
"ARRAY"A[1:N,1:N];
"ARRAY" TR,TI[1:N-1];
ENTRY: THE REAL PART OF THE UPPER TRIANGLE OF THE
HERMITIAN MATRIX MUST BE GIVEN IN THE UPPER
TRIANGULAR PART OF A (THE ELEMENTS A[I,J], I<=J);
THE IMAGINARY PART OF THE STRICT LOWER TRIANGLE
OF THE HERMITIAN MATRIX MUST BE GIVEN IN THE
STRICT LOWER PART OF A (THE ELEMENTS A[I,J],I>J);
EXIT: DATA FOR THE BACKTRANSFORMATION;
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE MATRIX;
D: <ARRAY IDENTIFIER>;
"ARRAY"D[1:N];
EXIT : THE MAIN DIAGONAL OF THE RESULTING SYMMETRIC
TRIDIAGONAL MATRIX;
B: <ARRAY IDENTIFIER>;
"ARRAY"B[1:N-1];
EXIT: THE CODIAGONAL ELEMENTS OF THE RESULTING SYMMETRIC
TRIDIAGONAL MATRIX;
BB: <ARRAY IDENTIFIER>;
"ARRAY"BB[1:N-1];
EXIT : THE SQUARES OF THE MODULI OF THE CODIAGONAL
ELEMENTS OF THE RESULTING SYMMETRIC TRIDIAGONAL
MATRIX;
EM: <ARRAY IDENTIFIER>;
"ARRAY"EM[0:1];
ENTRY: EM[0], THE MACHINE PRECISION;
EXIT: EM[1], AN ESTIMATE FOR A NORM OF THE ORIGINAL
MATRIX.
PROCEDURES USED :
MATVEC = CP34011 ,
TAMVEC = CP34012 ,
MATMAT = CP34013 ,
TAMMAT = CP34014 ,
MATTAM = CP34015 ,
ELMVECCOL = CP34021 ,
ELMCOLVEC = CP34022 ,
ELMCOL = CP34023 ,
ELMROW = CP34024 ,
ELMVECROW = CP34026 ,
ELMROWVEC = CP34027 ,
ELMROWCOL = CP34028 ,
ELMCOLROW = CP34029 ,
CARPOL = CP34344 .
RUNNING TIME : PROPORTIONAL TO N CUBED .
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE: SEE HSHHRMTRIVAL (THIS SECTION).
SUBSECTION : BAKHRMTRI.
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE READS :
"PROCEDURE" BAKHRMTRI(A, N, N1, N2, VECR, VECI, TR, TI);
"VALUE" N, N1, N2; "INTEGER" N, N1, N2;
"ARRAY" A, VECR, VECI, TR, TI;
"CODE" 34365;
THE MEANING OF THE FORMAL PARAMETERS IS :
A,TR,TI: <ARRAY IDENTIFIER>;
"ARRAY"A[1:N,1:N];
"ARRAY" TR,TI[1:N-1];
ENTRY: THE DATA FOR THE BACKTRANSFORMATION AS PRODUCED
BY HSHHRMTRI;
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;
VECR,VECI: <ARRAY IDENTIFIER>;
"ARRAY" VECR,VECI[1:N,N1:N2];
ENTRY:
THE BACK TRANSFORMATION IS PERFORMED ON THE REAL
EIGENVECTORS GIVEN IN THE COLUMNS OF ARRAY VECR;
EXIT:
VECR : REAL PART OF THE TRANSFORMED EIGENVECTORS;
VECI : IMAGINARY PART OF THE TRANSFORMED EIGENVECTORS.
PROCEDURES USED :
MATMAT = CP34013 ,
TAMMAT = CP34014 ,
ELMCOL = CP34023 ,
ELMCOLROW = CP34029 ,
COMMUL = CP34341 ,
COMROWCST = CP34353 .
RUNNING TIME: PROPORTIONAL TO (N2-N1+1)*N**2 .
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE: SEE HSHHRMTRIVAL (THIS SECTION).
SUBSECTION : HSHHRMTRIVAL.
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE READS :
"PROCEDURE" HSHHRMTRIVAL(A, N, D, BB, EM); "VALUE" N; "INTEGER" N;
"ARRAY" A, D, BB, EM;
"CODE" 34364;
THE MEANING OF THE FORMAL PARAMETERS IS :
A: <ARRAY IDENTIFIER>;
"ARRAY"A[1:N,1:N];
ENTRY: THE REAL PART OF THE UPPER TRIANGLE OF THE
HERMITIAN MATRIX MUST BE GIVEN IN THE UPPER
TRIANGULAR PART OF A (THE ELEMENTS A[I,J], I<=J);
THE IMAGINARY PART OF THE STRICT LOWER TRIANGLE
OF THE HERMITIAN MATRIX MUST BE GIVEN IN THE
STRICT LOWER PART OF A (THE ELEMENTS A[I,J],I>J);
THE ELEMENTS OF A ARE ALTERED;
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE GIVEN MATRIX;
D: <ARRAY IDENTIFIER>;
"ARRAY"D[1:N];
EXIT: THE MAIN DIAGONAL OF THE RESULTING HERMITIAN
TRIDIAGONAL MATRIX;
BB: <ARRAY IDENTIFIER>;
"ARRAY"BB[1:N-1];
EXIT: THE SQUARES OF THE MODULI OF THE CODIAGONAL
ELEMENTS OF THE RESULTING HERMITIAN TRIDIAGONAL
MATRIX;
EM: <ARRAY IDENTIFIER>;
"ARRAY"EM[0:1];
ENTRY: EM[0],THE MACHINE PRECISION;
EXIT: EM[1], AN ESTIMATE FOR A NORM OF THE ORIGINAL
MATRIX;
PROCEDURES USED :
MATVEC = CP34011 ,
TAMVEC = CP34012 ,
MATMAT = CP34013 ,
TAMMAT = CP34014 ,
MATTAM = CP34015 ,
ELMVECCOL = CP34021 ,
ELMCOLVEC = CP34022 ,
ELMCOL = CP34023 ,
ELMROW = CP34024 ,
ELMVECROW = CP34026 ,
ELMROWVEC = CP34027 ,
ELMROWCOL = CP34028 ,
ELMCOLROW = CP34029 .
RUNNING TIME : PROPORTIONAL TO N CUBED .
LANGUAGE : ALGOL 60.
THE FOLLOWING HOLDS FOR THE THREE PROCEDURES :
METHOD AND PERFORMANCE :
HSHHRMTRIVAL TRANSFORMS A HERMITIAN MATRIX INTO A SIMILAR
HERMITIAN TRIDIAGONAL MATRIX BY MEANS OF HOUSEHOLDER'S
TRANSFORMATION.
HSHHRMTRI TRANSFORMS A HERMITIAN MATRIX INTO A SIMILAR
REAL TRIDIAGONAL MATRIX BY MEANS OF HOUSEHOLDER'S
TRANSFORMATION FOLLOWED BY A COMPLEX DIAGONAL UNITARY
SIMILARITY TRANSFORMATION IN ORDER TO MAKE THE RESULTING
TRIDIAGONAL MATRIX REAL SYMMETRIC;
HOUSEHOLDER'S TRANSFORMATION FOR COMPLEX HERMITIAN MATRICES
IS A UNITARY SIMILARITY TRANSFORMATION,TRANSFORMING A HERMITIAN
MATRIX INTO A SIMILAR COMPLEX TRIDIAGONAL ONE (SEE WILKINSON,
1965, P. 342-343). LET M BE A GIVEN HERMITIAN MATRIX OF ORDER
N, WITH REAL PART MR AND IMAGINARY PART MI, P THE
TRANSFORMING MATRIX AND T THE RESULTING HERMITIAN TRIDIAGONAL
MATRIX. SINCE P IS UNITARY, WE HAVE T = P"MP, WHERE
" STANDS FOR CONJUGATING AND TRANSPOSING. THE MATRIX P IS THE
PRODUCT OF N-2 HOUSEHOLDER MATRICES, THESE BEING UNITARY
HERMITIAN MATRICES OF THE FORM I-U"U/T, WHERE T IS A SCALAR
(>0), AND U A COMPLEX VECTOR. THE K-TH HOUSEHOLDER MATRIX,
K=1,...,N-2, IS CHOSEN IN SUCH A WAY THAT THE LAST K ELEMENTS OF U
VANISH, AND THE DESIRED ZEROS ARE INTRODUCED IN THE (N-K+1)-TH
COLUMN AND ROW OF THE MATRIX M. HOWEVER, IF THE EUCLIDIAN NORM
OF THE FIRST N-K-1 ELEMENTS OF COLUMN N-K+1 OF THE MATRIX M IS
SMALLER THAN THE MACHINE PRECISION TIMES THE INFINITY NORM OF THE
MATRIX ( NORM(MR) + NORM(MI) ), THEN THE K-TH TRANSFORMATION
IS SKIPPED (I.E. THE K-TH HOUSEHOLDER MATRIX IS REPLACED BY I).
THE COMPLEX DIAGONAL SIMILARITY TRANSFORMATION D TRANSFORMS THE
HERMITIAN TRIDIAGONAL MATRIX T INTO A REAL SYMMETRIC TRIDIAGONAL
MATRIX S (MUELLER, 1966). THE DIAGONAL OF D IS CHOSEN IN SUCH
A WAY THAT THE CODIAGONAL ELEMENTS OF T ARE TRANSFORMED INTO
THEIR ABSOLUTE VALUES.
BAKHRMTRI PERFORMS THE BACK TRANSFORMATION TO REPLACE THE
EIGENVECTORS OF THE TRIDIAGONAL SYMMETRIC MATRIX S BY THE
EIGENVECTORS OF THE ORIGINAL HERMITIAN MATRIX M. IF X IS AN
EIGENVECTOR OF S 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 K-TH HOUSEHOLDER
MATRIX TIMES V, FOR K=N-2,...,1. THE RESULTING VECTOR V 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 :
THE PROCEDURES HSHHRMTRIVAL AND BAKHRMTRI ARE USED IN SECTION
3.3.2.1. :
EIGVALHRM AND QRIVALHRM USE HSHHRMTRIVAL,
EIGHRM AND QRIHRM USE BAKHRMTRI .
AS A FORMAL TEST OF THE PROCEDURE HSHHRMTRI, THE FOLLOWING MATRIX
WAS USED (SEE GREGORY AND KARNEY, CHAPTER 6, EXAMPLE 6.6) :
3 1 0 +2I
1 3 -2I 0
0 +2I 1 1
-2I 0 1 1
"BEGIN"
"COMMENT" GREGORY AND KARNEY,CHAPTER 6, EXAMPLE 6.6;
"REAL" "ARRAY" A[1:4,1:4],D,B,BB[1:4],TR,TI[1:3],EM[0:1];
"INTEGER" I,J;
"PROCEDURE" OUT(S,A,N);
"VALUE" N;"INTEGER" N;"ARRAY" A;"STRING" S;
"BEGIN" "INTEGER" I,J;
OUTPUT(61,"("10S")",S);
"FOR" I:=1 "STEP" 1 "UNTIL" N "DO"
OUTPUT(61,"("+D.3DBB")",A[I]);
OUTPUT(61,"("/")")
"END" OUT;
INIMAT(1,4,1,4,A,0);
A[1,1]:=A[2,2]:=3;
A[1,2]:=A[3,3]:=A[3,4]:=A[4,4]:=1;
A[3,2]:=2;A[4,1]:=-2;
EM[0]:="-14;
OUTPUT(61,"(""("INITIAL MATRIX GIVEN IN ARRAY A[1:4,1:4]:")",/")");
"FOR" I:=1 "STEP" 1 "UNTIL" 4 "DO"
"BEGIN" "FOR" J:=1 "STEP" 1 "UNTIL" 4 "DO"
OUTPUT(61,"("-DBBB")",A[I,J]);
OUTPUT(61,"("/")")
"END";
OUTPUT(61,"("/,"("HSHHRMTRI DELIVERS:")",//")");
HSHHRMTRI(A,4,D,B,BB,EM,TR,TI);
OUT("("D[1:4]: ")",D,4);
OUT("("B[1:3]: ")",B,3);
OUT("("BB[1:3]: ")",BB,3);
OUT("("EM[1]: ")",EM,1);
"END"
OUTPUT :
INITIAL MATRIX GIVEN IN ARRAY A[1:4,1:4]:
3 1 0 0
0 3 0 0
0 2 1 1
-2 0 0 1
HSHHRMTRI DELIVERS:
D[1:4]: +3.000 +1.400 +2.600 +1.000
B[1:3]: +2.236 +0.800 +2.236
BB[1:3]: +5.000 +0.640 +5.000
EM[1]: +6.000
SOURCE TEXT(S) :
"CODE" 34363;
"CODE" 34365;
"CODE" 34364;