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;