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;