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;