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;