Release of report, "Preconditioned Conjugate-Gradient 2 (PCG2).  A computer program for solving ground-water flow equations"


                           UNITED STATES
                    DEPARTMENT OF THE INTERIOR
                         GEOLOGICAL SURVEY
                     Water Resources Division
                        Washington 25, D.C.

In reply refer to:                            September 20, 1990

GROUND WATER BRANCH MEMORANDUM NO. 90.08

SUBJECT:  PUBLICATIONS--Release of report, "Preconditioned
          Conjugate-Gradient 2 (PCG2).  A computer program for
          solving ground-water flow equations," by Mary C. Hill.

The subject report has recently been published as Water-Resources
Investigations Report 90-4048.  The report describes and documents
the program, PCG2, a numerical code which offers two previously
unavailable preconditioned conjugate-gradient methods to solve the
system of linear equations that are used to describe the
groundwater flow system using the modular three-dimensional,
finite-difference ground-water model (McDonald and Harbaugh, 1988,
U.S. Geological Survey Techniques of Water Resources
Investigations, Book 6, Chapter Al, A modular three-dimensional
finite-difference ground-water flow model).

The basic code of McDonald and Harbaugh (1988) gives the option of
solving the system of linear equations using either the Strongly
Implicit Procedure (SIP) or Slice-Successive Overrelaxation
(SSOR).  Logan Kuiper (1987, Computer program for solving
groundwater flow equations by the preconditioned conjugate
gradient method, U.S. Geological Survey Water-Resources
Investigations Report 87-4091) added the option of using the
method of preconditioned conjugate gradients and provided the
choice of five types of preconditioners:  three variants of
incomplete Choleski factorization, the point Jacobi, and block
Jacobi.  Kuiper's report indicates which of the preconditoners
tested were most successful in his experiments.

One of the appeals to the conjugate gradient method is that it is
not necessary to specify iteration parameters as is required for
SIP and SSOR.  The method of conjugate gradients is considered to
be an N-step iterative method in that it is an algorithm applied
to give successive approximations to a system of N linear
equations that will yield the solution in at most N steps if
computations could be done with complete accuracy.
"Preconditioning" in association with the method of conjugate
gradients, involves transforming the original system of linear
equations into a system of linear equations that hopefully has the
property that application of the conjugate gradient method to the
transformed set of equations will result in fewer steps being
needed to converge to a solution than would be needed for the
original system of equations.  Various preconditioners that may be
used with the method of conjugate gradients have been identified
in the "numerical" literature.  The recently released computer
code, PCG2, offers two preconditioners that previously have not
been available for use with the subject modular finite-difference
model (McDonald and Harbaugh, 1988): A modified incomplete
Choleski factorization and a least-squares polynomial
preconditioner.  Mary Hill reports that compared to other
preconditioners that require no greater computer storage, the
results of her test results suggest that the modified incomplete
Choleski factorization preconditioning is efficient on scalar
computers; and the least squares polynomial preconditioner, while
not as efficient as SIP or the modified incomplete Choleski on
scalar computers, is more efficient on vector computers.  The
preconditioners that she considered were "those that produce a
solver that has computer storage requirements less than or equal
to the strongly implicit procedure (SIP) as programmed for the
ground-water flow problem."

It is worth noting that in numerical experiments reported on by
Logan Kuiper (see "A comparison of iterative methods as applied to
the solution of the nonlinear three-dimensional groundwater flow
equation" by Logan K. Kuiper, SIAM J. Sci. Stat. Comput., vol 8,
no. 4, p. 521-528, July 1987) the preconditioned conjugate
gradient methods did better than SIP for most problems tested but
he reported for the two-dimensional test problem (he considered 5
test problems) SIP did as well as the preconditioned conjugate-
gradient methods; and Mary Hill (see "Solving ground water flow
problems by conjugate-gradient methods and the strongly implicit
procedure," by Mary Hill, Water Resources Research, vol. 26, no.
9, page 1961-1969, September 1990) found that SIP was sometimes
more efficient than the preconditioned conjugate gradient methods
that she tried for some three-dimensional and/or nonlinear flow
problems.  The results from these numerical studies suggest that
although the preconditioned conjugate gradient methods have been
shown to be efficient for many problems there are cases, that
cannot be determined beforehand, for which SIP will be the better
choice.  In other words, no one method always works best.

Water Resources Division employees may obtain the Computer
Program, PCG2, from the Software Exchange System (SOFTEX) on the
QVARSA Prime Computer.  The SOFTEX entry identifier for PCG2 is
COSALOOOO1.

We recommend that this information be brought to the attention of
technical and management personnel concerned with ground-water
studies.



                           (s) Thomas E. Reilly
                               Acting Chief,
                                  Office of Ground Water WRD

Distribution:
     A, B (memo only)
     S, FO, PO (memo and attachment)