NUMAL Section 3.2.1.1.1
BEGIN SECTION : 3.2.1.1.1 (June, 1974)
AUTHORS : T.J.DEKKER AND W.HOFFMANN.
CONTRIBUTORS: W.HOFFMANN, J.G.VERWER.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 731022.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS TWO PROCEDURES.
A) EQILBR EQUILIBRATES A MATRIX BY MEANS OF A DIAGONAL SIMILARITY
TRANSFORMATION,
B) BAKLBR PERFORMS THE CORRESPONDING BACK TRANSFORMATION ON THE
COLUMNS OF A MATRIX AND SHOULD BE CALLED AFTER EQILBR.
KEYWORDS:
SIMILARITY TRANSFORMATION,
EQUILIBRATION.
SUBSECTION: EQILBR.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" EQILBR(A, N, EM, D, INT); "VALUE" N;
"INTEGER" N; "ARRAY" A, EM, D; "INTEGER" "ARRAY" INT;
"CODE" 34173;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE GIVEN MATRIX;
A: <ARRAY IDENTIFIER>;
"ARRAY"A[1:N,1:N];
ENTRY: THE MATRIX TO BE EQUILIBRATED;
EXIT: THE EQUILIBRATED MATRIX;
EM: <ARRAY IDENTIFIER>;
"ARRAY"EM[0:0];
ENTRY: EM[0], THE MACHINE PRECISION;
D: <ARRAY IDENTIFIER>;
"ARRAY"D[1:N];
EXIT: THE MAIN DIAGONAL OF THE TRANSFORMING DIAGONAL
MATRIX;
INT: <ARRAY IDENTIFIER>;
"INTEGER""ARRAY" INT[1:N];
EXIT: INFORMATION DEFINING THE POSSIBLE INTERCHANGING OF
SOME ROWS AND THE CORRESPONDING COLUMNS;
PROCEDURES USED:
TAMMAT = CP34014,
MATTAM = CP34015,
ICHCOL = CP34031,
ICHROW = CP34032.
RUNNING TIME: ROUGHLY PROPORTIONAL TO N SQUARED.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE MATRIX IS EQUILIBRATED BY MEANS OF OSBORNE'S DIAGONAL
SIMILARITY TRANSFORMATION POSSIBLY WITH INTERCHANGES [2].
THE TRANSFORMING DIAGONAL MATRIX AND THE EQUILIBRATED MATRIX ARE
CALCULATED ITERATIVELY:
IN EACH STEP A CERTAIN COLUMN OF THE MATRIX IS MULTIPLIED BY, AND
THE CORRESPONDING ROW DIVIDED BY, A FACTOR WHICH IS CHOSEN IN SUCH
A WAY THAT THE CONSIDERED COLUMN AND ROW OBTAIN ROUGHLY THE SAME
EUCLIDEAN NORM (IN FACT, THE FACTOR IS ROUNDED TO THE NEAREST
INTEGRAL POWER OF 2, IN ORDER TO PREVENT ROUNDING ERRORS); THE
COLUMNS AND ROWS ARE HANDLED IN CYCLIC ORDER. IF THE MATRIX DOES
NOT CONTAIN COLUMNS OR ROWS WHOSE OFF-DIAGONAL ELEMENTS ARE 0 OR
NEARLY 0, THEN THE PROCESS (WITH UNROUNDED FACTORS) CONVERGES, AND
IN PRACTICE A FEW STEPS ARE NEEDED TO OBTAIN A REASONABLY
EQUILIBRATED MATRIX [2].
IF ALL OFF-DIAGONAL ELEMENTS OF SOME CONSIDERED COLUMN (ROW) ARE 0
OR NEARLY 0, THEN THIS COLUMN (ROW) IS INTERCHANGED WITH THE FIRST
NONZERO COLUMN (LAST NONZERO ROW) OF THE MATRIX, AND, IN ORDER TO
HAVE A SIMILARITY TRANSFORMATION, THE CORRESPONDING ROWS (COLUMNS)
ARE ALSO INTERCHANGED; THEN FOR THE FURTHER EQUILIBRATION, THE
SUBMATRIX IS CONSIDERED WHICH DOES NOT CONTAIN SUCH ZERO COLUMNS
AND ROWS AND THE CORRESPONDING ROWS AND COLUMNS. THE EQUILIBRATION
PROCESS IS CONTINUED UNTIL, IN A WHOLE CYCLE NO FACTOR > 2 OR < 0.5
AND NO ZERO COLUMN OR ROW IS FOUND, OR UNTIL (N + 1) * N ** 2 ROWS
AND COLUMNS HAVE BEEN CONSIDERED.
SUBSECTION: BAKLBR.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" BAKLBR(N, N1, N2, D, INT, VEC); "VALUE" N, N1, N2;
"INTEGER" N, N1, N2; "ARRAY" D, VEC; "INTEGER" "ARRAY" INT;
"CODE" 34174;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
THE LENGTH OF THE VECTORS TO BE TRANSFORMED;
N1, N2: <ARITHMETIC EXPRESSION>;
THE SERIAL NUMBERS OF THE FIRST AND LAST VECTOR TO BE
TRANSFORMED;
VEC: <ARRAY IDENTIFIER>;
"ARRAY"VEC[1:N,N1:N2];
ENTRY: THE N2 - N1 + 1 VECTORS OF LENGTH N TO BE
TRANSFORMED;
EXIT: THE N2 - N1 + 1 VECTORS OF LENGTH N RESULTING FROM
THE BACK TRANSFORMATION;
D: <ARRAY IDENTIFIER>;
"ARRAY"D[1:N];
ENTRY: THE MAIN DIAGONAL OF THE TRANSFORMING DIAGONAL
MATRIX OF ORDER N, AS PRODUCED BY EQILBR;
INT: <ARRAY IDENTIFIER>;
"INTEGER""ARRAY" INT[1:N];
ENTRY: INFORMATION DEFINING THE POSSIBLE INTERCHANGING OF
SOME ROWS AND COLUMNS, AS PRODUCED BY EQILBR.
PROCEDURES USED:
ICHROW = CP34032.
RUNNING TIME: ROUGHLY PROPORTIONAL TO (N2 - N1 + 1) * N.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE BACK TRANSFORMATION, WHICH CORRESPONDS WITH THE DIAGONAL
SIMILARITY TRANSFORMATION AS PERFORMED BY EQILBR, TRANSFORMS
A VECTOR X INTO A VECTOR DX AND PERFORMS THE CORRESPONDING
INTERCHANGES. THE MATRIX D IS THE DIAGONAL MATRIX OF THE DIAGONAL
SIMILARITY TRANSFORMATION.
REFERENCES:
[1] DEKKER, T. J. AND HOFFMANN, W.
ALGOL 60 PROCEDURES IN NUMERICAL ALGEBRA, PART 2,
MATHEMATICAL CENTRE TRACTS 23,
MATHEMATISCH CENTRUM, AMSTERDAM, 1968;
[2] OSBORNE, E. E, ON PRECONDITIONING OF MATRICES,
J. ACM 7(1960) 338-354.
EXAMPLES OF USE:
EXAMPLES OF USE OF EQILBR AND BAKLBR CAN BE FOUND IN THE PROCEDURES
FOR CALCULATING EIGENVALUES AND EIGENVECTORS AS DESCRIBED IN
SECTION 3.3.1.2.2.
SOURCE TEXT(S) :
"CODE" 34173;
"CODE" 34174;