NUMAL Section 3.5.1.2
BEGIN SECTION : 3.5.1.2 (July, 1974)
AUTHOR : D.T.WINTER
INSTITUTE : MATHEMATICAL CENTRE
RECEIVED : 731217
BRIEF DESCRIPTION :
THIS SECTION CONTAINS TWO PROCEDURES, QRISNGVAL AND QRISNGVALDEC.
QRISNGVAL CALCULATES THE SINGULAR VALUES OF A GIVEN MATRIX.
QRISNGVALDEC CALCULATES THE SINGULAR VALUES DECOMPOSITION
U * S * V', WITH U AND V ORTHOGONAL AND S POSITIVE DIAGONAL.
KEYWORDS :
SINGULAR VALUES
QR ITERATION
SUBSECTION : QRISNGVAL
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"INTEGER" "PROCEDURE" QRISNGVAL(A, M, N, VAL, EM);
"VALUE" M, N; "INTEGER" M, N; "ARRAY" A, VAL, EM;
"CODE" 34272;
THE MEANING OF THE FORMAL PARAMETERS IS :
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1:M,1:N];
ENTRY: THE INPUT MATRIX;
EXIT: DATA CONCERNING THE TRANSFORMATION TO BIDIAGONAL FORM;
M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF ROWS OF A;
N: <ARITHMETIC EXPRESSION>;
THE NUMBER OF COLUMNS OF A, N SHOULD SATISFY N <= M;
VAL: <ARRAY IDENTIFIER>;
"ARRAY" VAL[1:N];
EXIT: THE SINGULAR VALUES;
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[0:7];
ENTRY: EM[0]: THE MACHINE PRECISION;
EM[2]: THE RELATIVE PRECISION IN THE SINGULAR VALUES;
EM[4]: THE MAXIMAL NUMBER OF ITERATIONS TO BE PERFORMED;
EM[6]: THE MINIMAL NON-NEGLECTABLE SINGULAR VALUE;
EXIT: EM[1]: THE INFINITY NORM OF THE MATRIX;
EM[3]: THE MAXIMAL NEGLECTED SUPERDIAGONAL ELEMENT;
EM[5]: THE NUMBER OF ITERATIONS PERFORMED;
EM[7]: THE NUMERICAL RANK OF THE MATRIX, I.E. THE NUMBER OF
SINGULAR VALUES GREATER THAN OR EQUAL TO EM[6].
MOREOVER :
QRISNGVAL:= THE NUMBER OF SINGULAR VALUES NOT FOUND, I.E. A NUMBER
NOT EQUAL TO ZERO IF THE NUMBER OF ITERATIONS EXCEEDS EM[4].
PROCEDURES USED :
HSHREABID = CP34260
QRISNGVALBID = CP34270
REQUIRED CENTRAL MEMORY : AN AUXILIARY ARRAY OF N REALS IS DECLARED
RUNNING TIME :
THE RUNNING TIME DEPENDS UPON THE PROPERTIES OF THE MATRIX, HOWEVER
THE PROCESS OF BIDIAGONALIZATION DOMINATES, AND ITS RUNNING TIME
IS PROPORTIONAL TO (M + N) * N * N
METHOD AND PERFORMANCE :
THE MATRIX IS FIRST TRANSFORMED TO BIDIAGONAL FORM BY THE PROCEDURE
HSHREABID (SECTION 3.2.2.1.1) , AND THEN THE SINGULAR VALUES ARE
CALCULATED BY QRISNGVALBID (SECTION 3.5.1.1).
LANGUAGE : ALGOL 60
SUBSECTION : QRISNGVALDEC
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"INTEGER" "PROCEDURE" QRISNGVALDEC(A, M, N, VAL, V, EM);
"VALUE" M, N; "INTEGER" M, N; "ARRAY" A, VAL, V, EM;
"CODE" 34273;
THE MEANING OF THE FORMAL PARAMETERS IS:
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1:M,1:N];
ENTRY: THE GIVEN MATRIX;
EXIT: THE MATRIX U IN THE SINGULAR VALUES DECOMPOSITION
U * S * V';
M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF ROWS OF A;
N: <ARITHMETIC EXPRESSION>;
THE NUMBER OF COLUMNS OF A, N SHOULD SATISFY N <= M;
VAL: <ARRAY IDENTIFIER>;
"ARRAY" VAL[1:N];
EXIT: THE SINGULAR VALUES;
V: <ARRAY IDENTIFIER>;
"ARRAY" V[1:N,1:N];
EXIT: THE MATRIX V OF THE SINGULAR VALUES DECOMPOSITION
(A = U . S . V' );
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[0:7];
ENTRY: EM[0]: THE MACHINE PRECISION;
EM[2]: THE RELATIVE PRECISION IN THE SINGULAR VALUES;
EM[4]: THE MAXIMAL NUMBER OF ITERATIONS TO BE PERFORMED;
EM[6]: THE MINIMAL NON-NEGLECTABLE SINGULAR VALUE;
EXIT: EM[1]: THE INFINITY NORM OF THE MATRIX;
EM[3]: THE MAXIMAL NEGLECTED SUPER DIAGONAL ELEMENT;
EM[5]: THE NUMBER OF ITERATIONS PERFORMED;
EM[7]: THE NUMERICAL RANK OF THE MATRIX, I.E. THE NUMBER OF
SINGULAR VALUES GREATER THAN OR EQUAL TO EM[6].
MOREOVER :
QRISNGVALDEC:= THE NUMBER OF SINGULAR VALUES NOT FOUND, I.E. A
NUMBER NOT EQUAL TO ZERO IF THE NUMBER OF ITERATIONS EXCEEDS
EM[4].
PROCEDURES USED :
HSHREABID = CP34260
PSTTFMMAT = CP34261
PRETFMMAT = CP34262
QRISNGVALDECBID = CP34271
REQUIRED CENTRAL MEMORY : AN AUXILIARY ARRAY OF N ELEMENTS IS DECLARED
RUNNING TIME :
THE RUNNING TIME DEPENDS UPON THE PROPERTIES OF THE MATRIX, HOWEVER
THE PROCESS OF BIDIAGONALIZATION DOMINATES, AND ITS RUNNING TIME
IS PROPORTIONAL TO (M + N) * N * N
METHOD AND PERFORMANCE:
THE MATRIX IS FIRST TRANSFORMED TO BIDIAGONAL FORM BY THE PROCEDURE
HSHREABID (SECTION 3.2.2.1.1), THE TWO TRANSFORMING MATRICES ARE
CALCULATED BY THE PROCEDURES PSTTFMMAT AND PRETFMMAT (SECTIONS
3.2.2.1.2 AND 3.2.2.1.3 RESPECTIVELY), AND FINALLY THE SINGULAR
VALUES DECOMPOSITION IS CALCULATED BY QRISNGVALDECBID (SECTION
3.5.1.1).
LANGUAGE : ALGOL 60
REFERENCES :
WILKINSON, J.H. AND C.REINSCH
HANDBOOK OF AUTOMATIC COMPUTATION, VOL. 2
LINEAR ALGEBRA
HEIDELBERG (1971)
EXAMPLE OF USE :
AS THE PROCEDURE QRISNGVALDEC CALCULATES THE SINGULAR VALUES OF A
MATRIX IN EXACTLY THE SAME WAY AS QRISNGVAL, WE GIVE HER ONLY AN
EXAMPLE OF USE OF THE PROCEDURE QRISNGVALDEC. FIRST WE GIVE A
PROGRAM, AND THEN THE RESULTS OF THIS PROGRAM:
"BEGIN" "ARRAY" A[1:6,1:5], V[1:5,1:5], VAL[1:5], EM[0:7];
"INTEGER" I, J;
"FOR" I:= 1 "STEP" 1 "UNTIL" 6 "DO"
"FOR" J:= 1 "STEP" 1 "UNTIL" 5 "DO"
A[I,J]:= 1 / (I + J - 1);
EM[0]:= "-14; EM[2]:= "-12; EM[4]:= 25; EM[6]:= "-10;
I:= QRISNGVALDEC(A, 6, 5, VAL, V, EM);
OUTPUT(61, "("3B, "("NUMBER SINGULAR VALUES NOT FOUND : ")",
3ZD, /, 3B, "("INFINITY NORM : ")", N, /, 3B,
"("MAX NEGLECTED SUBDIAGONAL ELEMENT : ")", N, /, 3B,
"("NUMBER ITERATIONS : ")", 3ZD, /, 3B,
"("NUMERICAL RANK : ")", 3ZD, /")", I, EM[1], EM[3], EM[5],
EM[7]);
OUTPUT(61, "("/, 3B, "("SINGULAR VALUES : ")", /")");
"FOR" I:= 1 "STEP" 1 "UNTIL" 5 "DO"
OUTPUT(61, "("/, 3B, N")", VAL[I]);
OUTPUT(61, "("/, /, 3B, "("MATRIX U, FIRST 3 COLUMNS")", /")");
"FOR" I:= 1 "STEP" 1 "UNTIL" 6 "DO"
OUTPUT(61, "("/, 3B, 3(N)")", A[I,1], A[I,2], A[I,3]);
OUTPUT(61, "("/, /, 13B, "("LAST 2 COLUMNS")", /")");
"FOR" I:= 1 "STEP" 1 "UNTIL" 6 "DO"
OUTPUT(61, "("/, 13B, 2(N)")", A[I,4], A[I,5])
"END"
NUMBER SINGULAR VALUES NOT FOUND : 0
INFINITY NORM : +2.2833333333334"+000
MAX NEGLECTED SUBDIAGONAL ELEMENT : +5.7786437871158"-014
NUMBER ITERATIONS : 5
NUMERICAL RANK : 5
SINGULAR VALUES :
+1.5921172587262"+000
+2.2449595426097"-001
+1.3610556101029"-002
+4.3245382038374"-004
+6.4001947134260"-006
MATRIX U, FIRST 3 COLUMNS
-7.5497918208386"-001 +6.1011090790645"-001 -2.3287173869184"-001
-4.3909273679284"-001 -2.2602102994174"-001 +7.0245315582712"-001
-3.1703146681544"-001 -3.7306964696148"-001 +2.1607293656979"-001
-2.4999458583084"-001 -3.9557817833576"-001 -1.4665595223684"-001
-2.0704999076883"-001 -3.8483260608872"-001 -3.6803786187007"-001
-1.7699734614538"-001 -3.6458192866515"-001 -4.9868122801331"-001
LAST 2 COLUMNS
+5.8625326935176"-002 -1.0184205426735"-002
-4.8169088124009"-001 +1.7189132301455"-001
+5.4982292571999"-001 -5.9788920283495"-001
+4.0633053815463"-001 +4.5989617524697"-001
-6.1755991033503"-002 +4.3029765325422"-001
-5.4158416488948"-001 -4.6499203623570"-001
SOURCE TEXT(S):
"CODE" 34272;
"CODE" 34273;