NUMAL Section 3.1.2.1.1.1.2.1
BEGIN SECTION : 3.1.2.1.1.1.2.1 (June, 1974)
AUTHOR: W. HOFFMANN.
CONTRIBUTOR: J. C. P. BUS.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 731210.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS TWO PREPARATORY PROCEDURES FOR THE
SOLUTION OF SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS WITH A
TRIDIAGONAL MATRIX;
DECTRI PERFORMS A TRIANGULAR DECOMPOSITION OF A TRIDIAGONAL
MATRIX.
DECTRIPIV PERFORMS A TRIANGULAR DECOMPOSITION OF A TRIDIAGONAL
MATRIX, USING PARTIAL PIVOTING TO STABILIZE THE PROCESS.
KEYWORDS:
LU DECOMPOSITION,
TRIANGULAR DECOMPOSITION,
TRIDIAGONAL MATRIX.
SUBSECTION: DECTRI.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"PROCEDURE" DECTRI(SUB, DIAG, SUPER, N, AUX);
"VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, AUX;
"CODE" 34423;
THE MEANING OF THE FORMAL PARAMETERS IS:
SUB: <ARRAY IDENTIFIER>;
"ARRAY" SUB[1: N - 1];
ENTRY: THE SUBDIAGONAL OF THE GIVEN MATRIX T, SAY;
T[I + 1, I] SHOULD BE GIVEN IN SUB[I], I = 1,
..., N - 1;
EXIT: SUPPOSE L DENOTES THE LOWER-BIDIAGONAL MATRIX, SUCH
THAT LU = T, FOR SOME UPPER-BIDIAGONAL MATRIX U,
WITH UNIT DIAGONAL ELEMENTS, THEN L[I + 1, I] WILL
BE DELIVERED IN SUB[I], I = 1, ..., AUX[3] - 1;
DIAG: <ARRAY IDENTIFIER>;
"ARRAY" DIAG[1: N];
ENTRY: THE DIAGONAL OF T;
EXIT: L[I, I] WILL BE DELIVERED IN DIAG[I], I = 1, ...,
AUX[3];
SUPER: <ARRAY IDENTIFIER>;
"ARRAY" SUPER[1: N - 1];
ENTRY: THE SUPERDIAGONAL OF T; T[I, I + 1] SHOULD BE GIVEN
IN SUPER[I], I = 1, ..., N - 1;
EXIT: U[I, I + 1] WILL BE DELIVERED IN SUPER[I], I = 1,
..., AUX[3] - 1;
N: <ARITHMETICAL EXPRESSION>;
THE ORDER OF THE MATRIX;
AUX: <ARRAY IDENTIFIER>;
"ARRAY" AUX[2:5];
ENTRY :
AUX[2]: A RELATIVE TOLERANCE; A REASONABLE CHOICE FOR THIS
VALUE IS AN ESTIMATE OF THE RELATIVE PRECISION OF
THE MATRIX ELEMENTS, HOWEVER, IT SHOULD NOT BE
CHOSEN SMALLER THAN THE MACHINE PRECISION;
EXIT:
AUX[3]: THE NUMBER OF ELIMINATION STEPS PERFORMED;
AUX[5]: IF AUX[3] = N, THEN AUX[5] WILL EQUAL THE INFINITY-
NORM OF THE MATRIX, ELSE AUX[5] IS SET EQUAL TO
THE VALUE OF THAT ELEMENT WHICH CAUSES THE
BREAKDOWN OF THE DECOMPOSITION.
PROCEDURES USED: NONE.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE METHOD USED IN DECTRI YIELDS A LOWER-BIDIAGONAL MATRIX L AND A
UNIT UPPER-BIDIAGONAL MATRIX U, SUCH THAT THE PRODUCT LU EQUALS THE
GIVEN TRIDIAGONAL MATRIX; THE PROCESS IS TERMINATED IN THE K-TH
STEP, IF THE MODULUS OF THE K-TH DIAGONAL ELEMENT IS SMALLER THAN A
CERTAIN SMALL VALUE, WHICH IS GIVEN BY AUX[2] MULTIPLIED BY THE
1-NORM OF THE K-TH ROW; IN THIS CASE AUX[3] WILL BE GIVEN THE VALUE
K - 1 AND AUX[5] WILL BE GIVEN THE VALUE OF THE K-TH DIAGONAL
ELEMENT.
EXAMPLE OF USE: SEE DECSOLTRI (SECTION 3.1.2.1.1.1.2.3).
SUBSECTION: DECTRIPIV.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"PROCEDURE" DECTRIPIV(SUB, DIAG, SUPER, N, AID, AUX, PIV);
"VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, AID, AUX;
"BOOLEAN" "ARRAY" PIV;
"CODE" 34426;
THE MEANING OF THE FORMAL PARAMETERS IS:
SUB: <ARRAY IDENTIFIER>;
"ARRAY" SUB[1: N - 1];
ENTRY: THE SUBDIAGONAL OF THE GIVEN MATRIX T, SAY;
T[I+1,I] SHOULD BE GIVEN IN SUB[I],I > 1,...,N - 2
EXIT: LET T' DENOTE THE MATRIX T WITH PERMUTED ROWS;
SUPPOSE L DENOTES THE LOWER-BIDIAGONAL MATRIX, SUCH
THAT LU = T', FOR SOME UNIT UPPER-TRIANGULAR MATRIX
U, THEN L[I + 1, I] WILL BE DELIVERED IN SUB[I],
I = 1, ..., AUX[3] - 1; NOTE THAT U HAS TWO
CODIAGONALS, BECAUSE OF THE PARTIAL PIVOTING DURING
THE DECOMPOSITION;
DIAG: <ARRAY IDENTIFIER>;
"ARRAY" DIAG[1: N];
ENTRY: THE DIAGONAL OF T;
EXIT: L[I,I] WILL BE DELIVERED IN DIAG[I],I=1,...,AUX[3];
SUPER: <ARRAY IDENTIFIER>;
"ARRAY" SUPER[1: N - 1];
ENTRY: THE SUPERDIAGONAL OF T; T[I, I + 1] SHOULD BE GIVEN
IN SUPER[I], I = 1, ..., N - 1;
EXIT: U[I, I + 1] WILL BE DELIVERED IN SUPER[I], I = 1,
..., AUX[3] - 1;
N: <ARITHMETICAL EXPRESSION>;
THE ORDER OF THE MATRIX;
AID: <ARRAY IDENTIFIER>;
"ARRAY" AID[1: N - 2];
EXIT:U[I,I+2] WILL BE DELIVERED IN AID[I],I=1,...,AUX[3]-2;
AUX: <ARRAY IDENTIFIER>;
"ARRAY" AUX[2:5];
ENTRY:
AUX[2]: A RELATIVE TOLERANCE; A REASONABLE CHOICE FOR THIS
VALUE IS AN ESTIMATE OF THE RELATIVE PRECISION OF
THE MATRIX ELEMENTS, HOWEVER, IT SHOULD NOT BE
CHOSEN SMALLER THAN THE MACHINE PRECISION;
EXIT:
AUX[3]: THE NUMBER OF ELIMINATION STEPS PERFORMED;
AUX[5]: IF AUX[3] = N, THEN AUX[5] WILL EQUAL THE INFINITY-
NORM OF THE MATRIX, ELSE AUX[5] IS SET EQUAL TO
THE VALUE OF THAT ELEMENT WHICH CAUSES THE
BREAKDOWN OF THE DECOMPOSITION.
PIV: <ARRAY IDENTIFIER>;
"BOOLEAN""ARRAY" PIV[1 : N - 1];
THE VALUE OF PIV[I] WILL BE TRUE IF THE I-TH AND (I + 1)-TH
ROW ARE INTERCHANGED, I = 1, ..., MIN(AUX[3], N - 1), ELSE
PIV[I] WILL BE FALSE.
PROCEDURES USED: NONE.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE METHOD USED IN DECTRIPIV YIELDS A LOWER-BIDIAGONAL MATRIX L AND
A UNIT UPPER-TRIANGULAR MATRIX U WITH TWO CODIAGONALS, SUCH THAT
THE PRODUCT LU EQUALS THE GIVEN TRIDIAGONAL MATRIX WITH PERMUTED
ROWS; PARTIAL PIVOTING IS USED DURING THE TRIANGULAR DECOMPOSITION,
I.E. THAT ELEMENT OF THE K-TH COLUMN OF L IS CHOSEN AS PIVOT IN THE
K-TH STEP, WHOSE MODULUS DIVIDED BY THE 1-NORM OF THE CORRESPONDING
ROW OF THE GIVEN MATRIX IS MAXIMAL; THE PROCESS IS TERMINATED IN
THE K-TH STEP, IF THE MODULUS OF THE K-TH PIVOT ELEMENT IS LESS
THAN A CERTAIN SMALL VALUE, WHICH IS GIVEN BY AUX[2] MULTIPLIED BY
THE 1-NORM OF THE CORRESPONDING ROW; IN THIS CASE AUX[3] WILL BE
GIVEN THE VALUE K - 1, AND AUX[5] WILL BE GIVEN THE VALUE OF THE
K-TH PIVOT ELEMENT.
EXAMPLE OF USE: SEE SOLTRIPIV (SECTION 3.1.2.1.1.1.2.3).
SOURCE TEXTS:
"CODE" 34423;
"CODE" 34426;