NUMAL Section 3.1.2.2.1
BEGIN SECTION : 3.1.2.2.1 (December, 1975)
AUTHOR: P.W.HEMKER.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 730615.
BRIEF DESCRIPTION:
CONJ GRAD SOLVES A LINEAR SYSTEM OF EQUATIONS BY THE METHOD OF
CONJUGATE GRADIENTS. THE SYSTEM HAS TO BE SYMMETRIC AND POSITIVE
DEFINITE.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE READS:
"PROCEDURE" CONJ GRAD (MATVEC, X, R, L, N, GO ON, ITERATE, NORM2);
"VALUE" L, N; "BOOLEAN" GO ON; "INTEGER" L, N, ITERATE;
"REAL" NORM2; "ARRAY" X, R; "PROCEDURE" MATVEC;
"CODE" 34220;
THE MEANING OF THE FORMAL PARAMETERS IS:
MATVEC: <PROCEDURE IDENTIFIER>;
THE HEADING OF THIS PROCEDURE READS:
"PROCEDURE" MATVEC( P, Q); "ARRAY" P, Q;
THIS PROCEDURE DEFINES THE MATRIX A (THE COEFFICIENT MATRIX
OF THE SYSTEM) AS FOLLOWS :
AT EACH CALL MATVEC DELIVERS IN Q THE MATRIX-VECTOR PRODUCT
AP; P AND Q ARE ONE - DIMENSIONAL ARRAYS:
"ARRAY" P,Q[L:N];
X: <ARRAY IDENTIFIER>;
"ARRAY" X[L:N];
ENTRY: AN INITIAL APPROXIMATION TO THE SOLUTION X;
EXIT: THE SOLUTION;
R: <ARRAY IDENTIFIER>;
"ARRAY" R[L:N];
ENTRY: THE RIGHT-HAND SIDE OF THE SYSTEM;
EXIT: THE RESIDUE B - AX, COMPUTED RECURSIVELY;
L,N: <ARITHMETIC EXPRESSION>;
L AND N ARE RESPECTIVELY THE LOWER AND UPPER BOUND OF THE
ARRAYS X,R,P,Q;
GO ON: <BOOLEAN EXPRESSION>;
GO ON INDICATES THE CONTINUATION OF THE PROCESS.
THIS EXPRESSION MAY DEPEND ON THE JENSEN PARAMETERS ITERATE
AND NORM2. WITH THIS BOOLEAN EXPRESSION THE USER CONTROLS
THE CONTINUATION OF THE PROCESS. IF GO ON:= "FALSE" THE
ITERATION PROCESS IS STOPPED.
ITERATE:<IDENTIFIER>;
DELIVERS THE NUMBER OF ITERATION STEPS ALREADY PERFORMED;
NORM2: <IDENTIFIER>;
DELIVERS THE SQUARED EUCLIDEAN NORM OF THE RESIDUE,COMPUTED
RECURSIVELY
PROCEDURES USED:
VECVEC = CP34010 ,
ELMVEC = CP34020 .
REQUIRED CENTRAL MEMORY:
EXECUTION FIELD LENGTH: 7 + 2 * ( N - L + 1 ).
RUNNING TIME:
THE RUNNING TIME IS PROPORTIONAL TO THE NUMBER OF ITERATION STEPS
PERFORMED. EACH ITERATION STEP REQUIRES ONE EVALUATION OF THE
PROCEDURE MATVEC, THE EVALUATION OF TWO SCALAR - VECTOR - PRODUCTS
AND ONE VECTOR - VECTOR - PRODUCT.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE: SEE REF[1].
REFERENCES:
[1].J.K.REID.
ON THE METHOD OF CONJUGATE GRADIENTS FOR THE SOLUTION OF LARGE
SPARSE SYSTEMS OF LINEAR EQUATIONS.
IN:LARGE SPARSE SETS OF LINEAR EQUATIONS (J.K.REID ED)1971.
EXAMPLE OF USE:
"BEGIN"
"ARRAY" X,B[0:12];
"INTEGER" IT,I;
"REAL" NO;
"PROCEDURE" A(X,B);
"ARRAY" X,B;
"BEGIN" B[0]:=2*X[0]-X[1];
"FOR" I:=1 "STEP" 1 "UNTIL" 11 "DO"
B[I]:=-X[I-1]+2*X[I]-X[I+1];
B[12]:=2*X[12]-X[11]
"END" A;
"FOR" I:=0 "STEP" 1 "UNTIL" 12 "DO" X[I]:=B[I]:=0;
B[0]:=1;B[12]:=4;
CONJ GRAD(A,X,B,0,12,IT<20 "AND" NO>"-10,IT,NO);
OUTPUT(61,"(""("IT= ")",B3D5B,"("NO= ")",N,//,10B,
"("X")",20B,"("R")",//")",IT,NO);
"FOR" I:=0 "STEP" 1 "UNTIL" 12 "DO"
OUTPUT(61,"("N,5B,N,/")",X[I],B[I])
"END"
DELIVERS:
IT= 013 NO= +3.3424581859911"-027
X R
+1.2142857142857"+000 -7.1054273576010"-015
+1.4285714285715"+000 +1.5151278924296"-014
+1.6428571428572"+000 -1.3184703260130"-014
+1.8571428571429"+000 +1.6718441615946"-014
+2.0714285714286"+000 -1.5514524667596"-014
+2.2857142857144"+000 +2.2130179956186"-014
+2.5000000000001"+000 -2.2524167805437"-014
+2.7142857142858"+000 +2.0834049529361"-014
+2.9285714285715"+000 -1.8674557504802"-014
+3.1428571428572"+000 +1.9163204503355"-014
+3.3571428571429"+000 -1.2366043539824"-014
+3.5714285714286"+000 +8.2548347242718"-015
+3.7857142857143"+000 +4.4408920985006"-016 .
SOURCE TEXT(S):
"CODE" 34220;