NUMAL Section 3.1.1.3.1.3
BEGIN SECTION : 3.1.1.3.1.3 (December, 1975)
AUTHOR : D.T.WINTER
INSTITUTE : MATHEMATICAL CENTRE
RECEIVED : 731217
BRIEF DESCRIPTION :
THIS SECTION CONTAINS 2 PROCEDURES FOR THE
CALCULATION OF THE HOMOGENEOUS EQUATIONS A * X = 0 AND X' * A = 0,
WHERE A DENOTES A MATRIX, AND X A VECTOR:
HOMSOLSVD ASSUMES THAT THE SINGULAR VALUES DECOMPOSITION OF A HAS
BEEN GIVEN.
HOMSOL FIRST CALCULATES THE SINGULAR VALUES
DECOMPOSITION BY MEANS OF THE PROCEDURE QRISNGVALDEC.
KEYWORDS :
HOMOGENEOUS SOLUTION
SINGULAR VALUES
SUBSECTION : HOMSOLSVD
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"PROCEDURE" HOMSOLSVD(U, VAL, V, M, N);
"VALUE" M, N; "INTEGER" M, N; "ARRAY" U, VAL, V;
"CODE" 34284;
THE MEANING OF THE FORMAL PARAMETERS IS :
U: <ARRAY IDENTIFIER>;
"ARRAY" U[1:M,1:N];
ENTRY:
THE MATRIX U IN THE SINGULAR VALUES DECOMPOSITION A=U*S*V'.
EXIT: THE COLUMNS OF U THAT CORRESPOND TO THE ELEMENTS
OF VAL WITH A VALUE SMALLER THAN SOME SMALL CONSTANT MAY BE
SEEN AS THE SOLUTIONS OF X' * A = 0;
VAL: <ARRAY IDENTIFIER>;
"ARRAY" VAL[1:N];
ENTRY:THE SINGULAR VALUES;
EXIT :THE ARRAY WILL BE ORDERED IN SUCH A WAY THAT
VAL[I] < VAL[J] IF J < I;
V: <ARRAY IDENTIFIER>;
"ARRAY" V[1:N,1:N];
ENTRY:THE MATRIX V IN THE SINGULAR VALUES DECOMPOSITION;
EXIT:THE COLUMNS OF V THAT CORRESPOND TO THE ELEMENTS OF VAL
THAT ARE SMALLER THAN SOME SMALL CONSTANT MAY BE SEEN AS THE
SOLUTIONS OF THE EQUATION A * X = 0;
M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF ROWS OF U;
N: <ARITHMETIC EXPRESSION>;
THE NUMBER OF COLUMNS OF U;
PROCEDURES USED :
ICHCOL = CP34031
RUNNING TIME : PROPORTIONAL TO N ' 2
METHOD AND PERFORMANCE :
THE PROCEDURE DOES NOTHING MORE THAN A SIMPLE SORTING PROCESS ON
THE ELEMENTS OF THE ARRAY VAL, AT THE SAME TIME THE COLUMNS OF U
AND V ARE INTERCHANGED, ACCORDING TO THE INTERCHANGING OF THE
ELEMENTS VAL.
LANGUAGE : ALGOL 60
SUBSECTION : HOMSOL
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"INTEGER" "PROCEDURE" HOMSOL(A, M, N, V, EM);
"VALUE" M, N; "INTEGER" M, N; "ARRAY" A, V, EM;
"CODE" 34285;
HOMSOL:= THE NUMBER OF SINGULAR VALUES NOT FOUND, I.E. ZERO IF ALL
SINGULAR VALUES ARE CALCULATED.
THE MEANING OF THE FORMAL PAREMETERS IS :
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1:M,1:N];
ENTRY: THE MATRIX;
EXIT: THE COLUMNS OF A THAT CORRESPOND TO THE ELEMENTS OF
VAL THAT ARE SMALLER THAN SOME SMALL CONSTANT, MAY BE SEEN
AS THE SOLUTIONS OF THE EQUATION X' * A = 0.
M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF ROWS OF A.
N: <ARITHMETIC EXPRESSION>;
THE NUMBER OF COLUMNS OF A.
V: <ARRAY IDENTIFIER>;
"ARRAY" V[1:N,1:N];
EXIT: THE COLUMNS OF V THAT CORRESPOND TO ELEMENTS OF VAL
SMALLER THAN SOME SMALL CONSTANT MAY BE SEEN AS THE
SOLUTIONS OF THE EQUATION A * X = 0.
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[0:7];
ENTRY: EM[0]: THE MACHINE PRECISION;
EM[2]: THE RELATIVE PRECISION FOR THE SINGULAR VALUES;
EM[4]: THE MAXIMAL NUMBER OF ITERATIONS TO BE PERFORMED IN
THE SINGULAR VALUES DECOMPOSITION.
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 IN THE SINGULAR
VALUES DECOMPOSITION;
EM[7]: THE NUMERICAL RANK OF THE MATRIX, I.E. THE NUMBER OF
SINGULAR VALUES GREATER THAN OR EQUAL TO EM[6].
PROCEDURES USED :
QRISNGVALDEC = CP34273
HOMSOLSVD = CP34284
METHOD AND PERFORMANCE :
THE SOLUTION IS FOUND IN TWO STEPS :
1. THE SINGULAR VALUES DECOMPOSITION IS CALCULATED BY MEANS OF THE
PROCEDURE QRISNGVALDEC;
2. THE SINGULAR VALUES ARE ORDERED BY MEANS OF THE PROCEDURE
HOMSOLSVD (PROVIDED THAT ALL SINGULAR VALUES HAVE BEEN FOUND).
RUNNING TIME : ROUGHLY PROPORTIONAL TO (M + N) * N * N
LANGUAGE : ALGOL 60
REFERENCES :
WILKINSON, J.H. AND C.REINSCH
HANDBOOK OF AUTOMATIC COMPUTATION, VOL. 2
LINEAR ALGEBRA
HEIDELBERG (1971)
EXAMPLE OF USE :
FIRST WE GIVE A PROGRAM, AND THAN THE RESULTS OF THIS PROGRAM :
"BEGIN" "ARRAY" A[1:8,1:5], V[1:5,1:5], EM[0:7];
"INTEGER" I, J;
A[1,1]:=22; A[1,2]:= A[2,3]:=10; A[1,3]:= A[7,1]:= A[8,5]:=2;
A[1,4]:= A[3,5]:=3; A[1,5]:= A[2,2]:=7; A[2,1]:=14; A[2,5]:=8;
A[2,4]:= A[8,3]:=0; A[3,1]:= A[3,3]:= A[6,5]:=-1; A[3,2]:=13;
A[3,4]:=-11; A[4,1]:=-3; A[4,2]:= A[4,4]:= A[5,4]:= A[8,4]:=-2;
A[4,3]:=13; A[4,5]:= A[5,5]:= A[8,1]:=4; A[5,1]:= A[6,1]:=9;
A[5,2]:=8; A[5,3]:= A[6,2]:= A[7,5]:=1; A[6,3]:=-7;
A[6,4]:= A[7,4]:= A[8,2]:=5; A[7,2]:=-6; A[7,3]:=6;
EM[0]:="-14; EM[2]:="-12; EM[4]:=80; EM[6]:="-10;
I:= HOMSOL(A, 8, 5, V, EM);
OUTPUT(61, "("4B, "("NUMBER SINGULAR VALUES NOT FOUND : ")",
3ZD,/, 4B, "("NORM : ")", N,/, 4B, "("MAX NEGL SUBD ELEM : ")",
N,/, 4B, "("NUMBER ITERATIONS : ")", 3ZD, /, 4B, "("RANK : ")",
3ZD, /")", I, EM[1], EM[3], EM[5], EM[7]);
"FOR" J:= EM[7] + 1 "STEP" 1 "UNTIL" 5 "DO"
OUTPUT(61, "("/, 4B, "("COLUMN NUMBER : ")", D, 5(/ ,4B, 2(N)),
3(/, 4B, N), /")", J, A[1,J], V[1,J], A[2,J], V[2,J], A[3,J],
V[3,J], A[4,J], V[4,J], A[5,J], V[5,J], A[6,J], A[7,J], A[8,J])
"END"
NUMBER SINGULAR VALUES NOT FOUND : 0
NORM : +4.4000000000000"+001
MAX NEGL SUBD ELEM : +4.3977072741076"-014
NUMBER ITERATIONS : 6
RANK : 3
COLUMN NUMBER : 4
+3.4708599800002"-001 -4.1909548511171"-001
-6.0723369623011"-001 +4.4050912303713"-001
+1.2207461910546"-001 -5.2004549247434"-002
+6.1882574433898"-001 +6.7605914021670"-001
-4.6344371870996"-003 +4.1297730284731"-001
+3.3409859838125"-001
-3.3528410857408"-002
-1.3547246422274"-002
COLUMN NUMBER : 5
-2.5533109413182"-001 +0.0000000000000"+000
-1.7359809248754"-001 -4.1854806384909"-001
-2.2081225414163"-001 -3.4879005320758"-001
+4.1165471593410"-002 -2.4415303724531"-001
+9.2044247057656"-001 +8.0221712237742"-001
-2.8895953996492"-002
+6.1327596621994"-002
-4.9058079025100"-002
SOURCE TEXT(S):
"CODE" 34284;
"CODE" 34285;