NUMAL Section 3.5.1.1
BEGIN SECTION : 3.5.1.1 (December, 1975)
AUTHORS : G.H.GOLUB AND C.REINSCH
CONTRIBUTOR : D.T.WINTER
INSTITUTE : MATHEMATICAL CENTRE
RECEIVED : 731217
BRIEF DESCRIPTION :
THIS SECTION CONTAINS TWO PROCEDURES, QRISNGVALBID AND
QRISNGVALDECBID. BOTH PROCEDURES CALCULATE THE SINGULAR VALUES OF A
BIDIAGONAL MATRIX. MOREOVER, THE SECOND PROCEDURE CALCULATES THE
THE SINGULAR VALUES DECOMPOSITION OF A FULL MATRIX OF WHICH THE
BIDIAGONAL AND THE PRE- AND POSTMULTIPLYING MATRICES, AS CALCULATED
BY HSHREABID ARE GIVEN.
KEYWORDS :
SINGULAR VALUES
QR ITERATION
BIDIAGONAL MATRICES
SUBSECTION : QRISNGVALBID
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"INTEGER" "PROCEDURE" QRISNGVALBID(D, B, N, EM);
"VALUE" N; "INTEGER" N; "ARRAY" D, B, EM;
"CODE" 34270;
THE MEANING OF THE FORMAL PARAMETERS IS:
D: <ARRAY IDENTIFIER>;
"ARRAY" D[1:N];
ENTRY: THE DIAGONAL OF THE BIDIAGONAL MATRIX;
EXIT: THE SINGULAR VALUES;
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE SUPER DIAGONAL OF THE BIDIAGONAL MATRIX,IN B[1:N-1];
N: <ARITHMETIC EXPRESSION>;
THE LENGTH OF B AND D;
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[1:7];
ENTRY: EM[1]: THE INFINITY NORM OF THE MATRIX;
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[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 :
QRISNGVALBID:= 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 : NONE
REQUIRED CENTRAL MEMORY : NO AUXILIARY ARRAYS ARE DECLARED
RUNNING TIME :
THE RUNNING TIME DEPENDS STRONGLY UPON THE PROPERTIES OF THE MATRIX
METHOD AND PERFORMANCE :
THE METHOD IS DESCRIBED IN DETAIL IN [1]. THIS PROCEDURE IS A
REWRITING OF PART OF THE PROCEDURE SVD PUBLISHED THERE BY
G.H.GOLUB AND C.REINSCH.
LANGUAGE : ALGOL 60.
SUBSECTION : QRISNGVALDECBID
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"INTEGER" "PROCEDURE" QRISNGVALDECBID(D, B, M, N, U, V, EM);
"VALUE" M, N; "INTEGER" M, N; "ARRAY" D, B, U, V, EM;
"CODE" 34271;
THE MEANING OF THE FORMAL PARAMETERS IS :
D: <ARRAY IDENTIFIER>;
"ARRAY" D[1:N];
ENTRY: THE DIAGONAL OF THE BIDIAGONAL MATRIX;
EXIT: THE SINGULAR VALUES;
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE SUPER DIAGONAL OF THE BIDIAGONAL MATRIX,IN B[1:N-1];
M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF ROWS OF THE MATRIX U;
N: <ARITHMETIC EXPRESSION>;
THE LENGTH OF B AND D, THE NUMBER OF COLUMNS OF U AND THE
NUMBER OF COLUMNS AND ROWS OF V;
U: <ARRAY IDENTIFIER>;
"ARRAY" U[1:M,1:N];
ENTRY: THE PREMULTIPLYING MATRIX AS PRODUCED BY PRETFMMAT
(SECTION 3.2.2.1.1);
EXIT: THE PREMULTIPLYING MATRIX U OF THE SINGULAR VALUES
DECOMPOSITION U * S * V';
V: <ARRAY IDENTIFIER>;
"ARRAY" V[1:N,1:N];
ENTRY: THE TRANSPOSE OF THE POSTMULTIPLYING MATRIX AS PRODUCED
BY PSTTFMMAT (SECTION 3.2.2.1.1);
EXIT: THE TRANSPOSE OF THE POSTMULTIPLYING MATRIX V OF THE
SINGULAR VALUES DECOMPOSITION;
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[1:7];
ENTRY: EM[1]: THE INFINITY NORM OF THE MATRIX;
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[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 :
QRISNGVALDECBID:= 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 :
ROTCOL = CP34040
REQUIRED CENTRAL MEMORY : NO AUXILIARY ARRAYS ARE DECLARED
RUNNING TIME :
THE RUNNING TIME DEPENDS STRONGLY UPON THE PROPERTIES OF THE MATRIX
METHOD AND PERFORMANCE :
THE METHOD IS DESCRIBED IN DETAIL IN [1]. THIS PROCEDURE IS A
REWRITING OF PART OF THE PROCEDURE SVD PUBLISHED THERE BY
G.H.GOLUB AND C.REINSCH.
LANGUAGE : ALGOL 60
REFERENCES :
[1] WILKINSON, J.H. AND C.REINSCH
HANDBOOK OF AUTOMATIC COMPUTATION, VOL. 2
LINEAR ALGEBRA
HEIDELBERG (1971)
EXAMPLE OF USE :
FOR AN EXAMPLE OF USE ONE IS REFERRED TO SECTION 3.5.1.2
SOURCE TEXT(S):
"CODE" 34270;
"CODE" 34271;