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;