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;