NUMAL Section 3.1.1.1.1.3.3

BEGIN SECTION : 3.1.1.1.1.3.3 (, december 1978 )

AUTHORS : J.R.BUNCH,L.KAUFMAN,B.N.PARLETT.

CONTRIBUTOR : C.H.CONVENT.

INSTITUTE : UNIVERSITY OF AMSTERDAM.

RECEIVED : 770712.

BRIEF DESCRIPTION :

THIS SECTION CONTAINS TWO PROCEDURES :
A) SOLSYM2 SOLVES A SYMMETRIC SYSTEM OF LINEAR EQUATIONS, ASSUMING
    THAT THE MATRIX HAS BEEN DECOMPOSED INTO LDL' FORM BY A CALL OF
    DECSYM2;
B) DECSOLSYM2 CALCULATES THE LDL' DECOMPOSITION OF A SYMMETRIC
    MATRIX; MOREOVER, IF THIS MATRIX IS NON-SINGULAR, THEN IT SOLVES A
    CORRESPONDING SYSTEM OF LINEAR EQUATIONS;

KEYWORDS :

    GENERAL SYMMETRIC MATRIX,
    LDL' DECOMPOSITION,
    BLOCK DIAGONAL PIVOTING;


SUBSECTION : SOLSYM2.

CALLING SEQUENCE :

    THE HEADING OF THE PROCEDURE READS :
    "PROCEDURE" SOLSYM2(A,N,B,P,DETAUX);
    "VALUE" N;"INTEGER" N;
    "ARRAY" A,B,DETAUX;"INTEGER" "ARRAY" P;
    "CODE" 34292;

    THE MEANING OF THE FORMAL PARAMETERS IS :
    A :     <ARRAY IDENTIFIER>;
           "ARRAY" A[1:N,1:N];
           ENTRY : THE LDL' DECOMPOSITION OF A AS PRODUCED BY
                   DECSYM2;
    N :     <ARITHMETIC EXPRESSION>;
           THE ORDER OF THE MATRIX;
    B :     <ARRAY IDENTIFIER>;
           "ARRAY" B[1:N];
           ENTRY : THE RIGHT-HANDSIDE OF A SYSTEM OF LINEAR
                   EQUATIONS;
           EXIT  : THE CALCULATED SOLUTION VECTOR;
    P :     <ARRAY IDENTIFIER>;
           "INTEGER" "ARRAY" P[1:N];
           ENTRY : A VECTOR RECORDING THE INTERCHANGES PERFORMED ON
                   THE MATRIX BY THE PROCEDURE DECSYM2. P ALSO CONTAINS
                   INFORMATION ON THE BLOCKSTRUCTURE OF THE MATRIX AS
                   DECOMPOSED BY DECSYM2;
    DETAUX : <ARRAY IDENTIFIER>;
            "ARRAY" DETAUX[1:N];
            ENTRY : THE ARRAY DETAUX AS PRODUCED BY DECSYM2;

PROCEDURES USED :

    MATVEC=CP34011.
    ELMVECROW=CP34026.

RUNNING TIME : ROUGHLY PROPORTIONAL TO N**2.

METHOD AND PERFORMANCE :

    THE PROCEDURE SOLSYM2 COMPUTES THE SOLUTION OF A SYMMETRIC
    SYSTEM OF LINEAR EQUATIONS,ASSUMING THAT THE MATRIX HAS BEEN
    DECOMPOSED INTO LDL' FORM BY A CALL OF DECSYM2. B IS OVERWRITTEN
    WITH THE SOLUTION VECTOR.

REFERENCES :

    1) J.R.BUNCH,L.KAUFMAN.
      SOME STABLE METHODS FOR CALCULATING INERTIA AND SOLVING
      SYMMETRIC LINEAR SYSTEMS.
      MATHEMATICS OF COMPUTATION 31,P 163-180,1977.
    2) J.R.BUNCH,L.KAUFMAN,B.N.PARLETT.
      DECOMPOSITION OF A SYMMETRIC MATRIX.
      NUMERISCHE MATHEMATIK 27,P 95-109,1976.


SUBSECTION : DECSOLSYM2.

CALLING SEQUENCE :

    THE HEADING OF THE PROCEDURE READS :
    "PROCEDURE" DECSOLSYM2(A,N,B,TOL,AUX);
    "VALUE" N;"INTEGER" N;"REAL" TOL;
    "ARRAY" A,B;"INTEGER" "ARRAY" AUX;
    "CODE" 34293;

    THE MEANING OF THE FORMAL PARAMETERS IS :
    A :     <ARRAY IDENTIFIER>;
           "ARRAY" A[1:N,1:N];
           ENTRY : SEE DECSYM2;
           EXIT  : SEE DECSYM2;
    N :     <ARITHMETIC EXPRESSION>;
           THE ORDER OF THE MATRIX;
    B :     <ARRAY IDENTIFIER>;
           "ARRAY" B[1:N];
           ENTRY : SEE SOLSYM2;
           EXIT  : THE CALCULATED SOLUTION VECTOR,WHEN A WAS FOUND
                   TO BE NON-SINGULAR.
                   B IS LEFT UNDISTURBED OTHERWISE;
    TOL :   <ARITHMETIC EXPRESSION>;
           ENTRY : SEE DECSYM2;
    AUX :   <ARRAY IDENTIFIER>;
           "INTEGER" "ARRAY" AUX[2:5];
           EXIT  : SEE DECSYM2;

PROCEDURES USED :

    DECSYM2=CP34291.
    SOLSYM2=CP34292.

RUNNING TIME : ROUGHLY PROPORTIONAL TO N**3.

METHOD AND PERFORMANCE :

    THE PROCEDURE DECSOLSYM2 COMPUTES THE SOLUTION OF A SYMMETRIC
    SYSTEM OF LINEAR EQUATIONS. IT DOES SO BY FIRST CALLING THE
    PROCEDURE DECSYM2 TO COMPUTE THE LDL' DECOMPOSITION OF THE
    SYMMETRIC MATRIX,ACCORDING TO A METHOD DUE TO BUNCH,KAUFMAN AND
    PARLETT (SEE [1],[2]).
    WHEN THE MATRIX IS FOUND TO BE NON-SINGULAR THE PROCEDURE SOLSYM2
    IS CALLED TO COMPUTE THE SOLUTION VECTOR,AND THE LATTER OVERWRITES
    B. WHEN THE MATRIX IS FOUND TO BE SINGULAR THE PROCEDURE SOLSYM2
    IS NOT CALLED AND B IS LEFT UNDISTURBED.

REFERENCES :

    1) J.R.BUNCH,L.KAUFMAN.
      SOME STABLE METHODS FOR CALCULATING INERTIA AND SOLVING
      SYMMETRIC LINEAR SYSTEMS.
      MATHEMATICS OF COMPUTATION 31,P 163-180,1977.
    2) J.R.BUNCH,L.KAUFMAN,B.N.PARLETT.
      DECOMPOSITION OF A SYMMETRIC MATRIX.
      NUMERISCHE MATHEMATIK 27,P 95-109,1976.

EXAMPLES OF USE :

"BEGIN" "COMMENT" EXAMPLE OF USE OF THE PROCEDURE DECSOLSYM2;
        "INTEGER" I,J;"REAL" TOL;
        "REAL" "ARRAY" A[1:5,1:5],B[1:5];
        "INTEGER" "ARRAY" AUX[2:5];

        A[1,1]:=A[1,2]:=-3;A[1,3]:=-18;A[1,4]:=-30;A[1,5]:=18;
        A[2,2]:=-1;A[2,3]:=-4;A[2,4]:=-48;A[2,5]:=8;
        A[3,3]:=-6;A[3,4]:=-274;A[3,5]:=6;
        A[4,4]:=119;A[4,5]:=19;
        A[5,5]:=216;
        "FOR" I:=1 "STEP" 1 "UNTIL" 5 "DO"
        "FOR" J:=I+1 "STEP" 1 "UNTIL" 5 "DO" A[J,I]:=A[I,J];

        OUTPUT(61,"(""("THE COEFFICIENTMATRIX :")",/")");
        "FOR" I:=1 "STEP" 1 "UNTIL" 5 "DO"
        "BEGIN" "FOR" J:=1 "STEP" 1 "UNTIL" 5 "DO"
                OUTPUT(61,"("-2ZD,4B")",A[I,J]);
                OUTPUT(61,"("/")")
        OUTPUT(61,"("/,"("THE RHS-VECTOR :")",/")");
        "FOR" I:=1 "STEP" 1 "UNTIL" 5 "DO"
        "BEGIN" INREAL(70, B[I]);
                OUTPUT(61,"("-Z3D,4B")",B[I])
        "END";
        TOL:="-14;
        DECSOLSYM2(A,5,B,TOL,AUX);
        OUTPUT(61,"("2/")");
        "IF" AUX[2]=1 "THEN"
             OUTPUT(61,"(""("THE MATRIX IS SYMMETRIC")",/")")
        "ELSE" OUTPUT(61,"(""("THE MATRIX IS ASYMMETRIC.THE ")",
                           "("RESULTS ARE MEANINGLESS")",/")");
        OUTPUT(61,"("/,"("INERTIA : <")",D,"(",")",D,"(",")",D,
                    "(">")",/")",AUX[3],AUX[4],AUX[5]);
        OUTPUT(61,"("/,"("THE COMPUTED SOLUTION :")",/")");
        "FOR" I:=1 "STEP" 1 "UNTIL" 5 "DO"
        OUTPUT(61,"("-D.5D,4B")",B[I])
"END"

INPUT:

    327     291   1290     275    1720

THIS DELIVERS AS RESULT :

    THE COEFFICIENT MATRIX :
     -3      -3     -18    -30      18
     -3      -1      -4    -48       8
    -18      -4      -6   -274       6
    -30     -48    -274    119      19
     18       8       6     19     216

    THE RHS-VECTOR :
    327     291   1290     275    1720

    THE MATRIX IS SYMMETRIC.
    INERTIA : <3,2,0>

    THE COMPUTED SOLUTION :
    -7.00000   -2.00000   -1.00000    -4.00000     9.00000

SOURCE TEXT(S) :

"CODE" 34292;

"CODE" 34293;