NUMAL Section 3.2.1.2.1.2
BEGIN SECTION : 3.2.1.2.1.2 (June, 1974)
AUTHORS: T.J.DEKKER AND W.HOFFMANN.
CONTRIBUTORS: W.HOFFMANN, J.G.VERWER.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 731112.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS THREE PROCEDURES.
A) TFMREAHES TRANSFORMS A MATRIX INTO A SIMILAR UPPER-HESSENBERG
MATRIX BY MEANS OF WILKINSON'S TRANSFORMATION,
B) BAKREAHES1 PERFORMS THE CORRESPONDING BACK TRANSFORMATION ON
A VECTOR AND SHOULD BE CALLED AFTER TFMREAHES,
C) BAKREAHES2 PERFORMS THE CORRESPONDING BACK TRANSFORMATION ON
THE COLUMNS OF A MATRIX AND SHOULD BE CALLED AFTER TFMREAHES.
KEYWORDS:
SIMILARITY TRANSFORMATION,
UPPER-HESSENBERG MATRIX.
SUBSECTION: TFMREAHES.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" TFMREAHES(A, N, EM, INT); "VALUE" N;
"INTEGER" N; "ARRAY" A, EM; "INTEGER" "ARRAY" INT;
"CODE" 34170;
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 MATRIX TO BE TRANSFORMED;
EXIT: THE UPPER-HESSENBERG MATRIX IS DELIVERED IN THE
UPPER TRIANGLE AND THE FIRST SUBDIAGONAL OF A, THE
(NONTRIVIAL ELEMENTS OF THE) TRANSFORMING MATRIX,
L, IN THE REMAINING PART OF A, I.E. A[I,J] =
L[I,J + 1], FOR I = 3,...,N AND J = 1,...,I - 2;
EM: <ARRAY IDENTIFIER>;
"ARRAY"EM[0:1];
ENTRY: EM[0], THE MACHINE PRECISION;
EXIT: EM[1], THE INFINITY NORM OF THE ORIGINAL MATRIX;
INT: <ARRAY IDENTIFIER>;
"INTEGER""ARRAY" INT[1:N];
EXIT: THE PIVOTAL INDICES DEFINING THE STABILIZING ROW
AND COLUMN INTERCHANGES;
PROCEDURES USED:
MATVEC = CP34011,
MATMAT = CP34013,
ICHCOL = CP34031,
ICHROW = CP34032.
REQUIRED CENTRAL MEMORY:
EXECUTION FIELD LENGTH:
A ONE-DIMENSIONAL REAL ARRAY OF LENGTH N IS DECLARED.
RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
WILKINSON'S TRANSFORMATION IS A TRIANGULAR SIMILARITY
TRANSFORMATION WITH STABILIZING ROW AND COLUMN INTERCHANGES
TRANSFORMING A MATRIX, M, INTO AN UPPER-HESSENBERG MATRIX, H.
THE TRANSFORMING MATRIX IS THE PRODUCT OF A PERMUTATION MATRIX, P,
AND A UNIT LOWER-TRIANGULAR MATRIX, L. THE NONDIAGONAL ELEMENTS IN
THE FIRST COLUMN OF L ARE 0, AND THE ROW AND COLUMN INTERCHANGES
ARE CHOSEN IN SUCH A WAY THAT THE ABSOLUTE VALUE OF EACH ELEMENT
OF L IS AT MOST 1.
BECAUSE OF THE SPECIAL FORM OF L, THE MATRICES H AND L CAN BE
STORED TOGETHER IN THE ARRAY USED FOR THE MATRIX M (SEE CALLING
SEQUENCE). FOR FURTHER DETAILS SEE REFERENCE [1] AND [2].
SUBSECTION: BAKREAHES1.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" BAKREAHES1(A, N, INT, V); "VALUE" N;
"INTEGER" N; "ARRAY" A, V; "INTEGER" "ARRAY" INT;
"CODE" 34171;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
THE LENGTH OF THE VECTOR TO BE TRANSFORMED;
A: <ARRAY IDENTIFIER>;
"ARRAY"A[1:N,1:N];
ENTRY: THE (NONTRIVIAL ELEMENTS OF THE) TRANSFORMING
MATRIX, L, AS PRODUCED BY TFMREAHES MUST BE GIVEN
IN THE PART BELOW THE FIRST SUBDIAGONAL OF A,
I.E. A[I,J] = L[I,J + 1], FOR I = 3,...,N AND
J = 1,...,I - 2;
INT: <ARRAY IDENTIFIER>;
"INTEGER""ARRAY" INT[1:N];
ENTRY: PIVOTAL INDICES DEFINING THE STABILIZING ROW AND
COLUMN INTERCHANGES AS PRODUCED BY TFMREAHES;
V: <ARRAY IDENTIFIER>;
"ARRAY"V[1:N];
ENTRY: THE VECTOR TO BE TRANSFORMED;
EXIT: THE TRANSFORMED VECTOR.
PROCEDURES USED:
MATVEC = CP34011.
RUNNING TIME: ROUGHLY PROPORTIONAL TO N SQUARED.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE BACK TRANSFORMATION WHICH CORRESPONDS TO WILKINSON'S
TRANSFORMATION AS PERFORMED BY TFMREAHES TRANSFORMS A VECTOR, X,
INTO THE VECTOR PLX, WHERE PL IS THE TRANSFORMING MATRIX.
SUBSECTION: BAKREAHES2.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" BAKREAHES2(A, N, N1, N2, INT, VEC); "VALUE" N, N1, N2;
"INTEGER" N, N1, N2; "ARRAY" A, VEC; "INTEGER" "ARRAY" INT;
"CODE" 34172;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
THE LENGTH OF THE VECTORS TO BE TRANSFORMED;
N1, N2: <ARITHMETIC EXPRESSION>;
THE COLUMN NUMBERS OF THE FIRST AND LAST VECTOR TO BE
TRANSFORMED;
A: <ARRAY IDENTIFIER>;
"ARRAY"A[1:N,1:N];
ENTRY: THE (NONTRIVIAL ELEMENTS OF THE) TRANSFORMING
MATRIX, L, AS PRODUCED BY TFMREAHES MUST BE GIVEN
IN THE PART BELOW THE FIRST SUBDIAGONAL OF A,
I.E. A[I,J] = L[I,J + 1], FOR I = 3,...,N AND
J = 1,...,I - 2;
INT: <ARRAY IDENTIFIER>;
"INTEGER""ARRAY" INT[1:N];
ENTRY: PIVOTAL INDICES DEFINING THE STABILIZING ROW AND
COLUMN INTERCHANGES AS PRODUCED BY TFMREAHES;
VEC: <ARRAY IDENTIFIER>;
"ARRAY"VEC[1:N,N1:N2];
ENTRY: THE N2 - N1 + 1 VECTORS OF LENGTH N TO BE
TRANSFORMED;
EXIT: THE N2 - N1 + 1 VECTORS OF LENGTH N RESULTING FROM
THE BACK TRANSFORMATION;
PROCEDURES USED:
TAMVEC = CP34012,
ICHROW = CP34032.
REQUIRED CENTRAL MEMORY:
EXECUTION FIELD LENGTH:
IONAL REAL ARRAY OF LENGTH N IS DECLARED.
RUNNING TIME: ROUGHLY PROPORTIONAL TO (N2 - N1 + 1) * N * N.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
SEE SUBSECTION BAKREAHES1.
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] J. H. WILKINSON, THE ALGEBRAIC EIGENVALUE PROBLEM,
CLARENDON PRESS, OXFORD, 1965.
EXAMPLES OF USE:
EXAMPLES OF USE OF TFMREAHES, BAKREAHES1 AND BAKREAHES2 CAN BE
FOUND IN THE PROCEDURES FOR CALCULATING EIGENVALUES AND
EIGENVECTORS AS DESCRIBED IN SECTION 3.3.1.2.2.
SOURCE TEXT(S) :
"CODE" 34170;
"CODE" 34171;
"CODE" 34172;