NUMAL Section 3.2.2.1.1

BEGIN SECTION : 3.2.2.1.1 (December, 1975)

AUTHOR : D.T.WINTER

INSTITUTE : MATHEMATICAL CENTRE

RECEIVED : 731217

BRIEF DESCRIPTION :

    THIS SECTION CONTAINS THREE PROCEDURES :
    1.  HSHREABID.
        THIS PROCEDURE  TRANSFORMS  A GIVEN MATRIX  TO BIDIAGONAL FORM,
        BY PREMULTIPLYING  AND  POSTMULTIPLYING  THE GIVEN MATRIX  WITH
        ORTHOGONAL MATRICES.
    2.  PSTTFMMAT.
        THIS PROCEDURE CALCULATES THE  POSTMULTIPLYING  MATRIX FROM THE
        DATA GENERATED BY HSHREABID.
    3.  PRETFMMAT.
        THIS PROCEDURE  CALCULATES THE  PREMULTIPLYING  MATRIX FROM THE
        DATA GENERATED BY HSHREABID.

KEYWORDS :
    HOUSEHOLDER'S TRANSFORMATION
    BIDIAGONALISATION


SUBSECTION : HSHREABID

CALLING SEQUENCE :
    THE HEADING OF THE PROCEDURE IS :
    "PROCEDURE" HSHREABID(A, M, N, D, B, EM);
    "VALUE" M, N; "INTEGER" M, N; "ARRAY" A, D, B, EM;
    "CODE" 34260;

    THE MEANING OF THE FORMAL PARAMETERS IS :
    A:  <ARRAY IDENTIFIER>;
        "ARRAY" A[1:M,1:N];
        ENTRY: THE GIVEN MATRIX;
        EXIT: DATA CONCERNING THE  PREMULTIPLYING  AND  POSTMULTIPLYING
            MATRICES;
    M:  <ARITHMETIC EXPRESSION>;
        THE NUMBER OF ROWS OF THE GIVEN MATRIX;
    N:  <ARITHMETIC EXPRESSION>;
        THE NUMBER OF COLUMNS OF THE GIVEN MATRIX,
        N SHOULD SATISFY N <= M;
    D:  <ARRAY IDENTIFIER>;
        "ARRAY"D[1:N];
        EXIT: THE DIAGONAL OF THE BIDIAGONAL MATRIX;
    B:  <ARRAY IDENTIFIER>;
        "ARRAY"B[1:N];
        EXIT: THE SUPERDIAGONAL OF THE BIDIAGONAL MATRIX IS DELIVERED
        IN B[1:N-1];
    EM: <ARRAY IDENTIFIER>;
        "ARRAY"EM[0:1];
        ENTRY: EM[0]: THE MACHINE-PRECISION;
        EXIT: EM[1]: THE INFINITY NORM OF THE GIVEN MATRIX.

PROCEDURES USED :
    TAMMAT = CP34014
    MATTAM = CP34015
    ELMCOL = CP34023
    ELMROW = CP34024

RUNNING TIME :
    RUNNING TIME IS ROUGHLY PROPORTIONAL TO (M + N) * N * N

METHOD AND PERFORMANCE :
    LET  US  ASSUME  A  GIVEN  MATRIX  A[ 1:M , 1:N ],  WITH  M  >=  N.
    FIRSTLY WE PREMULTIPLY A WITH A HOUSEHOLDER MATRIX,  CHOSEN IN SUCH
    A WAY THAT THE FIRST COLUMN OF THE RESULTING MATRIX A' IS ZERO WITH
    THE EXCEPTION  OF THE FIRST  ELEMENT.  SECONDLY WE  POSTMULTIPLY A'
    WITH A  HOUSEHOLDER  MATRIX SO  THAT THE FIRST ROW OF THE RESULTING
    MATRIX  IS ZERO  WITH  THE EXCEPTION  OF  THE FIRST  TWO  ELEMENTS.
    NOW  WE REMOVE  THE FIRST ROW AND COLUMN,  AND REPEAT  THIS PROCESS
    UNTIL  THE  MATRIX  IS  TOTALLY  TRANSFORMED  TO  BIDIAGONAL  FORM.
    THIS  PROCEDURE  IS A  REWRITING  OF A PART  OF  THE PROCEDURE  SVD
    PUBLISHED  BY  G.H.GOLUB  AND  C.REINSCH[1]. HOWEVER IN CONTRAST TO
    THEIR PROCEDURE, HERE WE SKIP A TRANSFORMATION IF THE COLUMN OR ROW
    ON WHICH  OUR  ATTENTION  IS FOCUSSED  IS ALREADY  (NEARLY)  IN THE
    DESIRED FORM,  I.E.  IF THE SUM OF THE SQUARES OF THE ELEMENTS THAT
    OUGHT TO BE  ZERO  IS SMALLER THAN  A CERTAIN CONSTANT,  IN SVD THE
    TRANSFORMATION  IS  SKIPPED  ONLY  IF THE  NORM  OF THE FULL ROW OR
    COLUMN  IS SMALL ENOUGH.  OUR WAY SEEMS TO GIVE BETTER RESULTS,  AS
    SOME  ILL-DEFINED  TRANSFORMATIONS  ARE  SKIPPED.  MOREOVER,  IF  A
    TRANSFORMATION  IS  SKIPPED,   WE  DO  NOT  STORE  A  ZERO  IN  THE
    DIAGONAL  OR  SUPERDIAGONAL,  BUT  WE  STORE  THE VALUE  THAT WOULD
    HAVE  BEEN  FOUND  IF THE  COLUMN  OR  ROW  WAS IN THE DESIRED FORM
    ALREADY.

LANGUAGE : ALGOL-60


SUBSECTION : PSTTFMMAT

CALLING SEQUENCE :
    THE HEADING OF THE PROCEDURE IS :
    "PROCEDURE" PSTTFMMAT(A, N, V, B);
    "VALUE" N; "INTEGER" N; "ARRAY" A, V, B;
    "CODE" 34261;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    A:  <ARRAY IDENTIFIER>;
        "ARRAY"A[1:N,1:N];
        THE DATA  CONCERNING THE  POSTMULTIPLYING MATRIX,  AS GENERATED
        BY HSHREABID;
    N:  <ARITHMETIC EXPRESSION>;
        THE NUMBER OF COLUMNS AND ROWS OF A;
    V:  <ARRAY IDENTIFIER>;
        "ARRAY"V[1:N,1:N];
        EXIT: THE POSTMULTIPLYING MATRIX;
    B:  <ARRAY IDENTIFIER>;
        "ARRAY"B[1:N];
        THE SUPERDIAGONAL AS GENERATED BY HSHREABID.

PROCEDURES USED :
    MATMAT = CP34013
    ELMCOL = CP34023

RUNNING TIME :
    THE RUNNING TIME IS ABOUT PROPORTIONAL TO N ** 3

LANGUAGE : ALGOL 60


SUBSECTION : PRETFMMAT

CALLING SEQUENCE :
    THE HEADING OF THE PROCEDURE IS :
    "PROCEDURE" PRETFMMAT(A, M, N, D);
    "VALUE" M, N; "INTEGER" M, N; "ARRAY" A, D;
    "CODE" 34262;

    THE MEANING OF THE FORMAL PARAMETERS IS :
    A:  <ARRAY IDENTIFIER>;
        "ARRAY"A[1:M,1:N];
        ENTRY:  THE  DATA   CONCERNING  THE  PREMULTIPLYING  MATRIX  AS
            GENERATED BY HSHREABID
        EXIT : THE PREMULTIPLYING MATRIX.
    M:  <ARITHMETIC EXPRESSION>;
        THE NUMBER OF ROWS OF A.
    N:  <ARITHMETIC EXPRESSION>;
        THE NUMBER OF COLUMNS OF A, N SHOULD SATISFY N <= M.
    D:  <ARRAY IDENTIFIER>;
        "ARRAY"D[1:N];
        THE DIAGONAL AS GENERATED BY HSHREABID.

PROCEDURES USED :
    TAMMAT = CP34014
    ELMCOL = CP34023

RUNNING TIME :
    THE RUNNING TIME IS ABOUT PROPORTIONAL TO M * N * N

LANGUAGE : ALGOL-60

REFERENCES :
    [1] WILKINSON, J.H. AND C.REINSCH
        HANDBOOK FOR 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" 34260;
"CODE" 34261;
"CODE" 34262;