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;