NUMAL Section 3.1.1.1.1.2.3
BEGIN SECTION : 3.1.1.1.1.2.3 (May, 1974)
AUTHOR: T.J. DEKKER.
CONTRIBUTORS: S.P.N. VAN KAMPEN, J. KOK.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 731015.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS FOUR PROCEDURES:
A) CHLSOL2, FOR THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS IF THE
COEFFICIENT MATRIX HAS BEEN DECOMPOSED BY A CALL OF THE PROCEDURE
CHLDEC2, SECTION 3.1.1.1.1.2.1., OR CHLDECSOL2;
B) CHLSOL1, FOR THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS IF THE
COEFFICIENT MATRIX HAS BEEN DECOMPOSED BY A CALL OF THE PROCEDURE
CHLDEC1, SECTION 3.1.1.1.1.2.1., OR CHLDECSOL1;
C) CHLDECSOL2, FOR THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS BY
CHOLESKY'S SQUARE ROOT METHOD;
THE COEFFICIENT MATRIX HAS TO BE SYMMETRIC POSITIVE DEFINITE AND
MUST BE GIVEN IN THE UPPER TRIANGLE OF A TWO-DIMENSIONAL ARRAY;
D) CHLDECSOL1, FOR THE SOLUTION OF A SYSTEM OF LINEAR EQUATIONS BY
CHOLESKY'S SQUARE ROOT METHOD;
THE COEFFICIENT MATRIX HAS TO BE SYMMETRIC POSITIVE DEFINITE AND
MUST BE GIVEN COLUMNWISE IN A ONE-DIMENSIONAL ARRAY.
KEYWORDS:
LINEAR EQUATIONS,
POSITIVE DEFINITE SYMMETRIC MATRIX,
CHOLESKY DECOMPOSITION.
SUBSECTION: CHLSOL2.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" CHLSOL2(A, N, B); "VALUE" N; "INTEGER" N; "ARRAY" A, B;
"CODE" 34390;
THE MEANING OF THE FORMAL PARAMETERS IS:
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1:N,1:N];
ENTRY: THE UPPER-TRIANGULAR PART OF THE CHOLESKY MATRIX
AS PRODUCED BY CHLDEC2, SECTION 3.1.1.1.1.2.1., OR
CHLDECSOL2 (THIS SECTION), MUST BE GIVEN IN THE
UPPER TRIANGLE OF A;
EXIT: THE CONTENTS OF A ARE NOT CHANGED;
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE MATRIX;
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE RIGHT HAND SIDE OF THE SYSTEM OF LINEAR
EQUATIONS;
EXIT: THE SOLUTION OF THE SYSTEM.
PROCEDURES USED:
MATVEC = CP34011,
TAMVEC = CP34012.
RUNNING TIME: ROUGHLY PROPORTIONAL TO N SQUARED.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE PROCEDURE CHLSOL2 CALCULATES THE SOLUTION OF A SYSTEM OF LINEAR
EQUATIONS, PROVIDED THAT THE COEFFICIENT MATRIX HAS BEEN DECOMPOSED
BY A SUCCESSFUL CALL OF CHLDEC2 OR CHLDECSOL2;
THE SOLUTION IS OBTAINED BY CARRYING OUT THE FORWARD AND BACK
SUBSTITUTION WITH THE CHOLESKY MATRIX AND THE RIGHT HAND SIDE.
THE RIGHT HAND SIDE IS OVERWRITTEN BY THE SOLUTION BUT THE
ELEMENTS OF THE CHOLESKY MATRIX ARE NOT CHANGED, THUS SEVERAL
SYSTEMS OF LINEAR EQUATIONS WITH THE SAME COEFFICIENT MATRIX BUT
DIFFERENT RIGHT HAND SIDES CAN BE SOLVED BY SUCCESSIVE CALLS OF
CHLSOL2. SEE ALSO REF [1].
REFERENCES:
[1]. T.J. DEKKER.
ALGOL 60 PROCEDURES IN NUMERICAL ALGEBRA, PART 1.
MC TRACT 22, 1968, MATH. CENTR., AMSTERDAM.
EXAMPLE OF USE:
SEE EXAMPLE OF USE OF CHLINV2, SECTION 3.1.1.1.1.2.4.
SUBSECTION: CHLSOL1.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" CHLSOL1(A, N, B); "VALUE" N; "INTEGER" N; "ARRAY" A, B;
"CODE" 34391;
THE MEANING OF THE FORMAL PARAMETERS IS:
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1 : (N + 1) * N // 2];
ENTRY: THE UPPER-TRIANGULAR PART OF THE CHOLESKY MATRIX
AS PRODUCED BY CHLDEC1, SECTION 3.1.1.1.1.2.1., OR
CHLDECSOL1 (THIS SECTION), MUST BE GIVEN COLUMNWISE
IN ARRAY A;
EXIT: THE CONTENTS OF A ARE NOT CHANGED;
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE MATRIX;
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE RIGHT HAND SIDE OF THE SYSTEM OF LINEAR
EQUATIONS;
EXIT: THE SOLUTION OF THE SYSTEM.
PROCEDURES USED:
VECVEC = CP34010,
SEQVEC = CP34016.
RUNNING TIME: ROUGHLY PROPORTIONAL TO N SQUARED.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE PROCEDURE CHLSOL1 CALCULATES THE SOLUTION OF A SYSTEM OF LINEAR
EQUATIONS, PROVIDED THAT THE COEFFICIENT MATRIX HAS BEEN DECOMPOSED
BY A SUCCESSFUL CALL OF CHLDEC1 OR CHLDECSOL1;
SEVERAL SYSTEMS WITH THE SAME COEFFICIENT MATRIX BUT DIFFERENT
RIGHT HAND SIDES CAN BE SOLVED BY SUCCESSIVE CALLS OF CHLSOL1.
SEE ALSO METHOD AND PERFORMANCE OF CHLSOL2 (THIS SECTION).
EXAMPLE OF USE:
SEE EXAMPLE OF USE OF CHLINV1, SECTION 3.1.1.1.1.2.4.
SUBSECTION: CHLDECSOL2.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" CHLDECSOL2(A, N, AUX, B); "VALUE" N; "INTEGER" N;
"ARRAY" A, AUX, B;
"CODE" 34392;
THE MEANING OF THE FORMAL PARAMETERS IS:
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1:N,1:N];
ENTRY: THE UPPER TRIANGLE OF THE POSITIVE DEFINITE MATRIX
MUST BE GIVEN IN THE UPPER-TRIANGULAR PART OF A (THE
ELEMENTS A[I,J], I <= J);
EXIT: THE CHOLESKY DECOMPOSITION OF THE MATRIX IS
DELIVERED IN THE UPPER TRIANGLE OF A;
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE MATRIX;
AUX: <ARRAY IDENTIFIER>;
"ARRAY" AUX[2:3];
ENTRY: AUX[2]: A RELATIVE TOLERANCE USED TO CONTROL THE
CALCULATION OF THE DIAGONAL ELEMENTS; (SEE METHOD
AND PERFORMANCE OF CHLDEC2, SECTION 3.1.1.1.1.2.1);
NORMAL EXIT: AUX[3]:= N;
ABNORMAL EXIT: IF THE DECOMPOSITION CANNOT BE CARRIED OUT
BECAUSE THE MATRIX IS (NUMERICALLY) NOT POSITIVE
DEFINITE, AUX[3]:= K - 1, WHERE K IS THE LAST STAGE
NUMBER.
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE RIGHT HAND SIDE OF THE SYSTEM OF LINEAR
EQUATIONS;
EXIT: THE SOLUTION OF THE SYSTEM.
PROCEDURES USED:
CHLDEC2 = CP34310,
CHLSOL2 = CP34390.
RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE PROCEDURE CHLDECSOL2 SOLVES A SYSTEM OF LINEAR EQUATIONS WITH
A SYMMETRIC POSITIVE DEFINITE COEFFICIENT MATRIX BY CALLING
CHLDEC2, SECTION 3.1.1.1.1.2.1., AND, IF THIS CALL WAS
SUCCESSFUL, CHLSOL2 (THIS SECTION).
SEE ALSO CHLDEC2, SECTION 3.1.1.1.1.2.1.
EXAMPLE OF USE:
SEE EXAMPLE OF USE OF CHLDECINV2, SECTION 3.1.1.1.1.2.4.
SUBSECTION: CHLDECSOL1.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS:
"PROCEDURE" CHLDECSOL1(A, N, AUX, B); "VALUE" N; "INTEGER" N;
"ARRAY" A, AUX, B;
"CODE" 34393;
THE MEANING OF THE FORMAL PARAMETERS IS:
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1 : (N + 1) * N // 2];
ENTRY: THE UPPER-TRIANGULAR PART OF THE POSITIVE DEFINITE
SYMMETRIC MATRIX MUST BE GIVEN COLUMNWISE IN ARRAY A
(THE (I,J)-TH ELEMENT OF THE MATRIX MUST BE GIVEN IN
A[(J - 1) * J // 2 + I] FOR 1 <= I <= J <= N);
EXIT: THE CHOLESKY DECOMPOSITION OF THE MATRIX IS
DELIVERED COLUMNWISE IN A.
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE MATRIX;
AUX: <ARRAY IDENTIFIER>;
"ARRAY" AUX[2:3];
ENTRY: AUX[2]: A RELATIVE TOLERANCE USED TO CONTROL THE
CALCULATION OF THE DIAGONAL ELEMENTS;
NORMAL EXIT: AUX[3]:= N;
ABNORMAL EXIT: IF THE DECOMPOSITION CANNOT BE CARRIED OUT
BECAUSE THE MATRIX IS (NUMERICALLY) NOT POSITIVE
DEFINITE, AUX[3]:= K - 1, WHERE K IS THE LAST STAGE
NUMBER.
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE RIGHT HAND SIDE OF THE SYSTEM OF LINEAR
EQUATIONS;
EXIT: THE SOLUTION OF THE SYSTEM.
PROCEDURES USED:
CHLDEC1 = CP34311,
CHLSOL1 = CP34391.
RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE PROCEDURE CHLDECSOL1 SOLVES A SYSTEM OF LINEAR EQUATIONS WITH
A SYMMETRIC POSITIVE DEFINITE COEFFICIENT MATRIX BY CALLING
CHLDEC1, SECTION 3.1.1.1.1.2.1., AND, IF THIS CALL WAS
SUCCESSFUL, CHLSOL1 (THIS SECTION).
THE UPPER TRIANGLE OF THE COEFFICIENT MATRIX MUST BE STORED COLUMN-
WISE IN A ONE-DIMENSIONAL ARRAY.
SEE ALSO CHLDEC1, SECTION 3.1.1.1.1.2.1.
EXAMPLE OF USE:
SEE EXAMPLE OF USE OF CHLDECINV1, SECTION 3.1.1.1.1.2.4.
SOURCE TEXT(S) :
"CODE" 34390;
"CODE" 34391;
"CODE" 34392;
"CODE" 34393;