Analysis and improvement of the nonlinear
iterative techniques for groundwater flow
modelling utilising MODFLOW

Andrew Michael Durick
B. Eng (EnvEng) – Bachelor of Engineering in Environmental Engineering – Griffith University 1995

Master of Applied Science
(Research)
Centre of Statistical Science and Industrial Mathematics
Queensland University of Technology
Brisbane, Australia
July 2004


Statement of Original Authorship

The work contained in this thesis has not been previously submitted for a degree or diploma
at any other higher education institution. To the best of my knowledge and belief, the thesis
contains no material previously published or written by another person except where due
reference is made.

Signed:

Date:

ii


Acknowledgements
Firstly and most importantly I would like to extend my gratitude to my supervisor Dr

Ian Turner, whose enthusiasm and extensive knowledge made this research possible
in so many instances. Especially appreciated is the extra effort he put in to ensure
work was progressing even during personal crises for both of us.

I would also like to thank my associate supervisor Dr John Doherty, who provided
necessary feedback when required and has always provided me with a reality check
in the discipline of groundwater modelling.

The author also acknowledges the partial funding provided by the Queensland
Department of Natural Resources & Mines for course fees, the use of resources, and
the flexibility to take leave and work around study commitments.

The author would also like to thank the School of Mathematics at QUT for a
scholarship to ensure enrolment was active at the time of submission and adding the
required time to ensure quality in the work undertaken.

Thanks also go to Dr Kiran Bajracharya for his comments on the research

Finally, but no less importantly is the support of my family. It has been the support
of my wife Leisa, who has shouldered the majority of the household chores and the
caring for our children, which has allowed me to undertake and complete this work
as it was undertaken on a part-time basis. For this I am extremely grateful.

iii


Abstract
As groundwater models are being used increasingly in the area of resource
allocation, there has been an increase in the level of complexity in an attempt to
capture heterogeneity, complex geometries and detail in interaction between the

model domain and the outside hydraulic influences. As models strive to represent
the real world in ever increasing detail, there is a strong likelihood that the boundary
conditions will become nonlinear. Nonlinearities exist in the groundwater flow
equation even in simple models when watertable (unconfined) conditions are
simulated.

This thesis is concerned with how these nonlinearities are treated

numerically, with particular focus on the MODFLOW groundwater flow software
and the nonlinear nature of the unconfined condition simulation.

One of the limitations of MODFLOW is that it employs a first order fixed point
iterative scheme to linearise the nonlinear system that arises as a result of the finite
difference discretisation process, which is well known to offer slow convergence
rates for highly nonlinear problems.

However, Newton’s method can achieve

quadratic convergence and is more effective at dealing with higher levels of
nonlinearity. Consequently, the main objective of this research is to investigate the
inclusion of Newton’s method to the suite of computational tools in MODFLOW to
enhance its flexibility in dealing with the increasing complexity of real world
problems, as well as providing a more competitive and efficient solution
methodology.

Furthermore,

the

underpinning


linear

iterative solvers

that

MODFLOW currently utilises are targeted at symmetric systems and a consequence
of using Newton’s method would be the requirement to solve non-symmetric
Jacobian systems. Therefore, another important aspect of this work is to investigate
linear iterative solution techniques that handle such systems, including the newer
Krylov style solvers GMRES and BiCGSTAB.

To achieve these objectives a number of simple benchmark problems involving
nonlinearities through the simulation of unconfined conditions were established to
compare the computational performance of the existing MODFLOW solvers to the

iv


new solution strategies investigated here. One of the highlights of these comparisons
was that Newton’s method when combined with an appropriately preconditioned
Krylov solver was on average greater than 40% more CPU time efficient than the
Picard based solution techniques. Furthermore, a significant amount of this time
saving came from the reduction in the number of nonlinear iterations due to the
quadratic nature of Newton’s method. It was also found that Newton’s method
benefited more from improved initial conditions than Picard’s method. Of all the
linear iterative solvers tested, GMRES required the least amount of computational
effort. While the Newton method involves more complexity in its implementation,
this should not be interpreted as prohibitive in its application. The results here show

that the extra work does result in performance increase, and thus the effort is
certainly worth it.

v


Contents

1

Introduction .......................................................................................................... 1
1.1

2

Literature Review......................................................................................... 1

1.1.1

The Problem ......................................................................................... 1

1.1.2

MODFLOW ......................................................................................... 4

1.1.3

Review of Previous Work .................................................................... 6

1.2


Objectives of the Thesis ............................................................................. 11

1.3

Overview of the Thesis .............................................................................. 12

Computational Techniques for Groundwater Flow Modelling.......................... 14
2.1

Nonlinear Techniques ................................................................................ 14

2.1.1

Fixed Point Iteration........................................................................... 16

2.1.2

Newton Iteration (Newton’s Method)................................................ 18

2.1.3

Summary of Nonlinear Methods........................................................ 25

2.2

Numerical Solution Techniques of the Linearised System ........................ 26

2.2.1


Gaussian Elimination ......................................................................... 27

2.2.2

GMRES .............................................................................................. 28

2.2.3

Bi-CGSTAB....................................................................................... 31

2.2.4

LU Decomposition and Solve ............................................................ 34

2.2.5

Preconditioning .................................................................................. 35

2.3

Overview of Mathematical Model ............................................................. 38

2.3.1
2.4

General Groundwater Flow Equation ................................................ 39

Overview of Computational Model ........................................................... 43

2.4.1


Discretisation ..................................................................................... 43

2.4.2

Finite Difference Equations ............................................................... 46

2.5

The Two-dimensional Steady State Unconfined Flow Equation............... 52

2.6

Current Fixed-point Iteration within MODFLOW .................................... 54

vi


2.7
3

4

Code Implementation ......................................................................................... 55
3.1

Approach .................................................................................................... 55

3.2


Coding Philosophy ..................................................................................... 56

3.3

Code Options.............................................................................................. 57

3.4

Details of MODTest................................................................................... 58

3.4.1

Model used in the development of the code....................................... 62

3.4.2

Reflections on Picard and Newton Implementation .......................... 62

Results and Discussion....................................................................................... 65
4.1

Benchmark Problems ................................................................................. 65

4.2

Benchmark Problem 1................................................................................ 66

4.3

Benchmark Problem 2................................................................................ 71


4.4

Benchmark Problem 3................................................................................ 76

4.5

Discussion of Picard Method Results ........................................................ 80

4.5.1

Solver statistics for the Picard Method .............................................. 80

4.5.2

Summary of the Picard Method ......................................................... 89

4.6

Discussion of Newton Method Results ...................................................... 91

4.6.1

Solver Statistics for the Newton Method ........................................... 91

4.6.2

Summary of the Newton Method..................................................... 101

4.7

5

Issues in Applying Newton Method to MODFLOW................................. 54

Comparison of Picard and Newton Results ............................................. 102

Conclusions and Future Work.......................................................................... 110
5.1

Conclusions .............................................................................................. 110

5.2

Future Research Directions ...................................................................... 113

6

Bibliography..................................................................................................... 115

7

Appendix 1 ....................................................................................................... 119
File and Subroutine Descriptions ......................................................................... 119

8

Appendix 2 ....................................................................................................... 123
Key Subroutines written for Study....................................................................... 123

vii



List of Figures
Figure 2.1 – Neighbour Coordinates.......................................................................... 45
Figure 2.2– Row, column and layer ordering. ........................................................... 45
Figure 2.3– Face at location (i,j+1/2,k) ....................................................................... 47
Figure 3.1 – Flowchart for MODTest ........................................................................ 59
Figure 3.2 – Example of Solver_ops.in...................................................................... 60
Figure 4.1 – Active model grid and boundary conditions in Benchmark Problem 1. 68
Figure 4.2 – Head solution contours for Benchmark Problem 1................................ 69
Figure 4.3 – Model grid for Benchmark Problem 2................................................... 72
Figure 4.4 – Head solution contours for Benchmark Problem 2................................ 73
Figure 4.5 – Head solution surface for Benchmark Problem 2.................................. 74
Figure 4.6 – Model grid for Benchmark Problem 3................................................... 76
Figure 4.7 – Head solution contours for Benchmark Problem 3................................ 77
Figure 4.8 – Head solution surface for Benchmark Problem 3.................................. 78
Figure 4.9 – Comparison of Subspace and Time Required for Solution of PicardGMRES(m) ........................................................................................................ 86
Figure 4.10 – Comparison of Subspace and Time Required for Solution of Newton –
GMRES(m) ........................................................................................................ 95
Figure 4.11 – Outer Iteration Count and Total CPU time.......................................... 99
Figure 4.12 – Outer Iteration Count Compared to F ............................................ 105
Figure 4.13 – Comparison of Changes in F for Successive Iterations................. 107
Figure 4.14 – Outer Iteration Count Compared to Maximum Head Change........... 108

viii


List of Tables
Table 3.1 – Combinations of Nonlinear Techniques and Linear Solution Schemes . 57
Table 4.1 – Best Performance for each solver for Benchmark Problem 1................. 70

Table 4.2 - Best Performance for each solver for Benchmark Problem 2 ................. 74
Table 4.3 - Best Performance for each solver for Benchmark Problem 2 using
improved initial conditions ................................................................................ 75
Table 4.4 - Best Performance for each solver for Benchmark Problem 3 ................. 78
Table 4.5 - Best Performance for each solver for Benchmark Problem 3 using
improved initial conditions ................................................................................ 79
Table 4.6 – Results of Picard and Gaussian Elimination ........................................... 81
Table 4.7 – Results of Picard and Gaussian Elimination using closer Initial
Conditions .......................................................................................................... 81
Table 4.8 – Results of Picard and GMRES................................................................ 81
Table 4.9 – Results of Picard and GMRES with the closer Initial Conditions .......... 83
Table 4.10 – Results of Picard and GMRES Restarted.............................................. 84
Table 4.11 – Results of Picard and GMRES Restarted with the closer Initial
Conditions .......................................................................................................... 87
Table 4.12 – Results of Picard and BiCGSTAB ........................................................ 88
Table 4.13 – Results of Picard and BiCGSTAB with the closer Initial Conditions .. 88
Table 4.14 – Results of Picard and LUDecomp......................................................... 89
Table 4.15 – Results of Picard and LUDecomp with the closer Initial Conditions ... 89
Table 4.16 – Results of Newton and Gaussian Elimination....................................... 91
Table 4.17 – Results of Newton and Gaussian Elimination with the closer Initial
Conditions .......................................................................................................... 91
Table 4.18 – Results of Newton and GMRES ........................................................... 92
Table 4.19 – Summary of Krylov Subspace Dimension for each Outer Iteration ..... 93
Table 4.20 – Results of Newton and GMRES with the closer Initial Conditions...... 93
Table 4.21 – Results of Newton and GMRES Restarted ........................................... 94
Table 4.22 – Results of Newton and GMRES Restarted with the closer Initial
Conditions .......................................................................................................... 96

ix



Table 4.23 – Results of Newton and BiCGSTAB ..................................................... 97
Table 4.24 – Results of Newton and BiCGSTAB with the closer Initial Conditions 97
Table 4.25 –Results of Newton and LUDecomp ....................................................... 98
Table 4.26 – Results of Newton and LUDecomp with the Improved Initial
Conditions ........................................................................................................ 100
Table 4.27 – Summary of Average Solver Improvement from Improved Initial
Conditions (Benchmark Problem 2)................................................................. 103
Table 4.28 – Ratio of successive F between Picard and Newton methods.......... 106

x


Chapter 1

1

Introduction

1.1

Literature Review

The utilisation of groundwater models in commercial applications has seen an
increase in complexity as models attempt to capture heterogeneity, complex
geometries, and the integration of complex data sets representing detail in boundary
conditions. However, this increase in model complexity has led to more nonlinearity
in the mathematical equations used to simulate groundwater flow.

1.1.1


The Problem

Nonlinearity in the formulation of the groundwater flow problem occurs when the
conditions being simulated have watertable (unconfined) characteristics, or when the
actions on the aquifer from boundary influences involve a function of the aquifer
head that is nonlinear.

The governing equation for groundwater flow in three

dimensions is:
∂ 
∂h  ∂ 
∂h 
∂h  ∂ 
∂h
 +  K zz
,
 K xx  +  K yy
 −W = Ss
∂x 
∂x  ∂y 
∂z 
∂y  ∂z 
∂t

(1.1)


where Kxx, Kyy, and Kzz are values of hydraulic conductivity along the x,y, and z

coordinates respectively (units of [Lt-1]), Ss is the term representing specific storage
of the porous medium measured in [L-1], h is the term representing potentiometric
head with the units of [L], t refers to time, and W is a source/sink term expressed as a
volumetric flux with the units of [t-1].

Equation (1.1) is derived in full in Section

2.3.1, and the reader is directed there for more detail.

When an aquifer system is modelled, the three-dimensional aquifer is conceptualised
into aquifer layers, which are further discretised into model nodes [1]. Flow between
these nodes is defined by two parameters that describe the aquifer’s ability to store
and transmit water. These terms are referred to as storativity and transmissivity
respectively. Transmissivity is defined as the hydraulic conductivity (K) of the
aquifer material multiplied by the saturated thickness (b), such that
T = Kb .

(1.2)

In this case, the governing equation for groundwater flow in the aquifer layer
becomes:
∂h
∂  ∂h  ∂  ∂h 
.
 Txx  +  Tyy  − W = Sc
∂t
∂x  ∂x  ∂y  ∂y 

(1.3)


Note that the ‘z’ dimension is not considered within the layer approach and the
storage term has become storage coefficient (Sc = Ssb). When the aquifer layer is
modelled as confined, saturated thickness remains constant and thus, the
transmissivity also remains constant.

In unconfined conditions the saturated

thickness can vary. The elevation of the bottom of the aquifer, and the head in the
aquifer are required to calculate the saturated thickness (b). The governing equation
in the unconfined layer approach can be written as:
∂ 
∂h  ∂ 
∂h
∂h 
,
 K xx h  +  K yy h  − W = S y
∂x 
∂x  ∂y 
∂t
∂y 

2

(1.4)


where the storage term is replaced with its unconfined counterpart - specific yield. It
is realised that the following can be written:

∂h ∂h 2

=
∂x
∂x
,
∂h ∂h 2
2h
=
∂y
∂y
2h

(1.5)

and thus equation (1.4) can be expressed in the form:
∂h
∂h 2 
∂ 
∂h 2  ∂ 
 = 2 S y
 +  K yy
 K xx
+ 2W .
∂t
∂y 
∂x 
∂x  ∂y 

(1.6)

The nonlinear nature of equation (1.6) comes from the fact that the head terms on the

left hand side are raised to the second power, while the head term on the right hand
side is only to the first power [1].

The numerical solution of nonlinear problems involves a process of iteration where
head values are changed such that they satisfy both the head dependent boundary
conditions (such as the stream interaction example above) and the unconfined head
and resulting flow in the aquifer. Typically, the approach to solving the nonlinear
problems can be split into what is usually termed outer and inner iterations. The
outer iterations are where the current estimate of the solution is used to set up any
model input that is dependent on the values in the solution. This modifies the system
of equations and gives a linearised representation using the current heads. The
solution then moves into the inner iteration, where the linearised system is solved
using linear iterative solution techniques.

It is the methods undertaken to address the nonlinearity of the equations that is the
focus of this work, particularly for the outer iteration of the nonlinear solution
structure. Strong nonlinearity can cause convergence of the iterative scheme to fail,
or can hinder convergence rates significantly. The addition of a variety of nonlinear

3


solution options gives the numerical tools more flexibility to deal with the nonlinear
nature of the equations and increases the likelihood that a solution can be achieved.

There is a plethora of pre-written software in existence (commercial and freely
distributed) specifically for the simulation of groundwater flow. Some of this code is
written to address concise aspects of groundwater flow, while others facilitate the
simulation of a variety of conditions. Of all the code available, the most popular and
hence most used is MODFLOW. The MODFLOW code is distributed by the United

States Geological Survey (USGS) and is freely downloadable from the their website
(www.usgs.h2o.com). MODFLOW has become the industry standard through its
simplicity and flexibility, and is used in the Queensland Department of Natural
Resources, Mines & Energy (NRM&E) for the simulation of groundwater flow.
NRM&E are primarily concerned with the modelling of regional scale aquifers for
the purposes of resource allocation and typically, model sizes are in the order of tens
of thousands of model cells (nodes) and involve complex model geometries and
watertable conditions.

1.1.2

MODFLOW

The MODFLOW code first appeared in the early 1980’s with development occurring
between 1981 and 1983.

A release with full documentation (USGS Open-File

Report) followed in early 1984. Its release coincided with the increase in general
availability of personal computers. MODFLOW has been updated throughout the
years following. The first major update since its release is often referred to as
MODFLOW 88 [2], which saw the code convert from FORTRAN66 to
FORTRAN77, and the addition of some add-on packages. The second major update
occurred in 1996, and saw the inclusion of additional packages to deal with the more
complex boundary conditions (such as Flow and Head Boundary Package,
Horizontal Flow Barrier update, Transient Leakage Package and Reservoir Package),
and also included updates to some of the numerical solvers available (such as
Preconditioned Conjugate Gradient version 2 update and the new Direct Solution
package). During this period there had been little change made to the core program,
with most of the changes in the form of new add-on packages.


4


In recent times MODFLOW2000 has appeared, which has involved significant
change to the operation of the code, as now the groundwater flow model is encased
into its own inverse problem solver for the purposes of calibration. Again the core
code and groundwater flow equations remain the same, and again there are new
additional packages available in this release responding to a need for further
complexity to the boundary packages.

MODFLOW’s modular nature and its ability to accommodate new packages with
little change to the core code was one of the design philosophies that the original
programmers adhered to. This allowed other hydrologists and programmers to code
up there own calculations for the representation of various boundary conditions, and
it is some of these external codes that have found there way into successive releases
of MODFLOW. The original programmers also tailored a design philosophy around
the hardware available at the time of the original release, thus they optimised the
code around the limited amount of memory available on most computers at the time.
These constraints led to the use of the Strongly Implicit Procedure (SIP) and the
Slice Successive Over Relaxation (SSOR) linear solvers in the original release.
These solvers were chosen as they conform to the memory usage requirements of
only four times the dimension of the problem.

However, the advancement of

computer technology (capacity and speed) and the corresponding advancement in
numerical techniques have meant that the concern of memory usage has reduced
considerably. This was shown with the MODFLOW2000 release that came with an
algebraic multi-grid method (LMG). This solver requires far more storage space as it

successively creates coarser grids and needs to retain these in the solution process.
In the report on this solver, the authors presented evidence that the constraints on
earlier versions of MODFLOW should not be adhered to, particularly when the LMG
solver can outperform the existing solvers in MODFLOW by two to twenty five
times [3].

Nonlinearity occurs in the unconfined (phreatic surface or watertable) condition as
head and flow are explicitly linked through the use of a variable transmissivity within
the internal calculations of MODFLOW. The transmissivity term is generated from

5


the user supplied hydraulic conductivity multiplied by the calculated saturated
thickness.

The saturated thickness in the unconfined situation is calculated by

subtracting the bottom elevation of the cell from the head in the cell.

The solvers in the first release of MODFLOW (SIP and SSOR) use a fixed-point
method to overcome nonlinearities. This iterative strategy uses at every iteration the
latest estimate of head values (from the previous iteration) to update the boundary
flows and transmissivity values in the flow equations for the current iteration. In the
MODFLOW88 release, a new Preconditioned Conjugate Gradient (PCG) method
that uses a modification of the fixed-point method is included. The modification sees
the definition of an outer and inner iteration where the update of boundary conditions
and transmissivity occurs in the outer iteration and this is followed by a series of
inner iterations until the solution converges, after which it returns to the outer
iteration again. Complete convergence is obtained if the count for the inner iteration

when the solution returns to the outer iteration is equal to one [4].

Currently the official releases of MODFLOW from the USGS deal with
nonlinearities through variations of the fixed-point iterative method, which is also
referred to as Picard Iteration. There are alternatives to the fixed-point approach, the
most popular being Newton’s method. In the literature the only instance where
MODFLOW has been linked directly to one of the Newton variants is MODFLOWSurfact. This is a commercial software package distributed by Hydrogeologic Inc.
and provides the user with the option to use Newton Linearisation with a
backtracking, or line searching, scheme to overcome nonlinearities tied in with an
adaptive time-stepping option.

1.1.3

Review of Previous Work

The majority of the available literature focusing on numerical methods for
groundwater flow modelling is on the solution of the linearised system.

The

literature highlights in many cases that a fixed-point method is used and it is the
linear solver that has been targeted for gains in speed and stability. This is expanded
upon in the following paragraphs.

6


Kuiper [5] compared the Strongly Implicit Procedure (SIP) and the Incomplete
Choleski Conjugate Gradient (ICCG) methods and used five two-dimensional
problems for testing, of which two were nonlinear ‘water table’ problems. The

problems utilised two-dimensional versions of the same equations that are now found
in MODFLOW. While Kuiper studied solving nonlinear problems, he only applied a
simple fixed-point method to the equations to account for the values in the
coefficient matrix being a function of head. This was applied to SIP at every
iteration, and to ICCG at various intervals of iterations.

In 1987, Kuiper [6] progressed to evaluations of three-dimensional problems using
the SIP and ICCG solvers, however this time both the Picard and Newton techniques
for dealing with nonlinearities were compared. The SIP solver was tested with both
nonlinear techniques, however the ICCG was limited to Picard, due to the need to
preserve symmetry of the coefficient matrix for the Choleski preconditioner. It was
found that the Picard iteration combined with the ICCG solver provided the best
performance in solving the three-dimensional nonlinear problem.

For the two-

dimensional nonlinear problem, the Newton and Picard SIP methods performed
equally as well as the Picard preconditioned conjugate gradient methods. In general it
was also found that there was little difference between the performance of the Picard
and Newton methods for line SOR or SIP [6]. This was an unexpected result and
probably due to the problem specifics. In particular, the starting value or initial
estimate used in the Newton method could have been too far away from the solution.

The convergence rate of a numerical method to solve a system of equations depends
on the spectral properties of the coefficient matrix. The spectral properties of a
coefficient matrix used in the Picard method are usually completely different from
the spectral properties of a Jacobian formed through application of Newton’s method
on a system of equations. Therefore, there must be other factors affecting the
performance of the Newton’s method in Kuiper’s 1987 work and while Kuiper [6]
didn’t achieve the success reported by other researchers with the Newton iterative

scheme for overcoming nonlinearities, it should be pointed out that the linear solvers
he was using were limited in their ability to solve asymmetrical matrix systems

7


resulting from application of Newton’s Method. Since then, significant advances
have been made in the solution of non-symmetric systems such as the Generalised
Minimisation RESidual (GMRES) [7] and Bi-stabilised Conjugate Gradient
(BiCGSTAB) methods [8].

Work in the field of unsaturated groundwater flow solving the Richard’s equation
has found Newton’s method to exhibit significant benefits over simple fixed point
methods and this is expanded upon in the next section.

In the literature the majority of work dealing with nonlinearities in relation to porous
media involves the solution of the unsaturated Richard’s equation.

The

methodologies and application of the nonlinear iterative procedures presented in the
unsaturated work are applicable to saturated flow models such as MODFLOW.

The Picard and Newton iteration schemes are discussed in detail in Section 2.1,
however it should be noted that comparisons have been made of the two methods in
the literature and these comparisons highlight the strengths and weakness of both
methods. Kuiper [6] found that Picard and Newton performed “approximately” the
same on the basis of the amount of computational effort required for determining the
solution.


Newton’s method, under the right conditions such as an initial iterate that is
sufficiently close to the solution, can be very effective at overcoming nonlinearities.
Paniconi et al. [9] in the process of overcoming the nonlinearities in an unsaturated
flow problem found that the Newton method can become quadratically convergent,
while the Picard method is limited to linear convergence rates. Newton’s method
needs this advantage, as it is more complex when compared computationally (in
terms of floating point operations) to the Picard scheme. Furthermore, Paniconi et al.
[9] found that the Newton method, on a per-iteration basis, is more expensive than
the Picard method, with the ‘per iteration CPU cost’ of the Picard method only half
that of the Newton method. This finding was also independent of the problem
dimension.

8


Implementation of the Full Newton method can be computationally expensive, due in
most part to the requirement of generating the Jacobian matrix. In evaluating the
Jacobian numerically, there exist opportunities to make the computations more
efficient, particularly due to local conservation of mass in the conductance of water
between neighbouring nodes. In fact, only the diagonal terms need evaluation, as the
off diagonal terms can be filled from components of the diagonal calculation in a
column-wise fashion. [10]

Variants of the Newton Method exist and involve selective updating of the slope
matrix and are usually employed when numerical computation of the Jacobian terms
is costly [11]. Paniconi et al. [11] found that successful convergence of the Newton
method is reliant on good initial solution estimates. This was also mentioned later by
Paniconi et al. [9] where it was reported that a poor initial estimate may result in
divergence.


Li [12] presented a simplified Newton Iteration, which utilises an

integrated hydraulic conductivity and the diffusion-dominated nature of the
unsaturated flow process. It was found that this approach converged faster than a
modified Picard scheme.

The Newton scheme had previously been limited by the available linear solvers, in
particular the inefficiency of linear solvers when dealing with large sparse nonsymmetric matrices. This problem has been rectified to some extent through the use
of Krylov subspace algorithms that have become increasingly reliable and efficient
[9].

While Newton’s method has faster convergence rates, the Picard method does
provide some advantages of its own. Paniconi et al. [11] found Picard to be simpler
to implement and on a per iteration basis it was less computationally costly. Picard
retains the symmetry of the coefficient matrix that arises from groundwater flow and
Paniconi et al. [9] describes how the Newton linearisation generates a non-symmetric
matrix (Jacobian), while the Picard preserves the symmetry.

Preservation of

symmetry allows for exploitation of more efficient storage schemes by certain linear
solvers. Both methods preserve the precise banded nature of the coefficient matrix,

9


however in an efficient storage scheme the Newton method would require more
storage due to loss of symmetry.

The aim of this work is to examine numerical methods that converge successfully

when the system becomes highly nonlinear and is difficult to solve. Panday et al.
[13] found that the Newton scheme shows it strength when dealing with high
nonlinearities and extreme heterogeneities, where often the Picard scheme performs
very poorly to the point of failure. Paniconi et al. [9] found that convergence rates
for Picard were slow, and even failed, when the problem involved complex time
varying boundary conditions, and strongly nonlinear characteristic equations.

Newton’s method also requires that the initial estimate be significantly close to the
actual solution, and for groundwater modelling this is likely to be the case [14].
During a transient simulation the initial iterate is sourced from the previous timestep,
and as groundwater movement is usually slow, it is likely that the solution at the
current timestep is going to be close to the preceding timestep. The quadratic
convergence rates associated with Newton’s Method are usually only applicable at
the local scale, which is suited to the transient simulation of groundwater [14].
Under steady state conditions, the initial estimate of the solution process can be
significantly away from the final converged solution, so it is expected that Newton’s
method may not exhibit the theoretical convergence rates initially, and may even fail
to converge.

A combined Picard-Newton approach has been suggested by Paniconi et al. [9] to
overcome the Newton method’s sensitivity to the solution starting point, exploiting
the strengths of each method. They produced a method that starts with the Picard
method to improve the initial solution estimate, then after certain criteria are met, the
Newton method is utilised for the solution. The switch is driven by a relative
reduction in the convergence rates. One slight disadvantage of this method is that it
requires both symmetric and non-symmetric storage schemes.

The work done by Hydrogeologic Inc for their code MODFLOW-Surfact involved
using a Newton linearisation with backtracking. Full Newton iterations have the


10


possibility of diverging given certain situations, however techniques can be used to
stabilise the solution. MODFLOW-Surfact overcomes oscillatory behaviour through
an under-relaxation formula, and backtracking provides further stability. Here the
L2-norm residual for the current solution and the preceding solution are compared
and if the residual is increasing, the update vector is shortened by a factor. This
process is repeated until the current iteration residual is an appropriate factor of the
previous one.

The solution then proceeds to the next Newton iteration.

The

additional computation involved in revisiting the solution is offset by the solvers
robustness with highly nonlinear problems.

The resulting asymmetrical matrix

system resulting from the application of the Newton iteration is solved in the
MODFLOW-Surfact code using an Orthomin solver. [15]

1.2

Objectives of the Thesis

The main objective of this thesis is to investigate the use of Newton’s method to
overcome the nonlinearities formed from the equations used in MODFLOW.
Current official releases of MODFLOW from the USGS only provide the fixed-point

/ Picard iteration for overcoming these nonlinearities. The addition of the Newton
method would provide more flexibility in MODFLOW’s approach to solving more
complex and sophisticated groundwater models where strong nonlinearities are
present in the formulation. It is thought that the Newton method would increase the
chance of achieving adequately converged solutions to the ever-increasing nonlinear
nature of complex model setups that are becoming commonplace in NRM&E.

Through the use of code written specifically for this study, Newton’s method is
compared to Picard’s method using a carefully chosen set of nonlinear benchmark
problems. The code written for the testing of the nonlinear options is controlled in
that it must represent the groundwater flow equation as it appears in the original
MODFLOW code, and it must allow for input of existing MODFLOW files. The
code developed for this thesis has been limited to two-dimensional model setups and
to maximise the difficulty in solution, the code solves steady state unconfined (water
table) problems.

11


The research sees the implementation of an inexact Newton method for the solution
of the MODFLOW equations. Inexact Newton methods employ some strategy to
approximate the Jacobian at each iteration and typically finite difference
approximations to the derivatives provide a good balance between accuracy and
efficiency. Furthermore, variations of the Inexact Newton method are investigated
that seek to minimise the number of times the complete Jacobian is generated and
factored during the outer iterations. The variants studied here include the Chord,
Shamanskii and Definitive Newton methods, which differ in the decision of when to
update the Jacobian matrix using the current solution.

Finally, from the realisation that the success of the nonlinear iteration method could

be reliant on the numerical method employed to solve the linearised system during
the inner iteration, the performance of four linear solvers has also been studied.
These solvers are two direct methods – Gaussian Elimination (GE) and Lower Upper
Decomposition (LUdecomp), and some Krylov based solvers – Bi-Conjugate
Gradient Stabilised (BiCGSTAB) and the Generalised Minimal Residual (GMRES)
method. The Krylov based solvers also link to some preconditioning options such as
Incomplete Lower Upper factorisation with zero infill (ILU(0)) and a simple SSOR
preconditioner on the coefficient matrix for the linearised system (from both Picard
and Newton).

1.3

Overview of the Thesis

The thesis comprises five chapters, each of which is outlined below.

Chapter 1 provides the background to the reasons why the research is being

undertaken. The reader is introduced to the MODFLOW code and explanations of
why the nonlinear options are being explored. The work undertaken in the area of
porous medium flow modelling and nonlinear methods is also presented. A clear
statement of the thesis objectives is also provided.

12


Chapter 2 presents an overview of the mathematical and computational models and

then details the techniques for overcoming nonlinearities and some of the numerical
solution schemes utilised in later chapters for testing the chosen benchmark

problems.

Chapter 3 details the implementation of the code written to test the various

nonlinear and numerical techniques.

Chapter 4 describes the set up of the benchmark problems used for testing the

nonlinear and numerical techniques. Discussions and analysis of the results of this
testing are also presented.

Chapter 5 summarises the work and provides the pros and cons of each

computational strategy investigated throughout the thesis.

The chapter also

recommends future research directions that it is felt would add value to the work
undertaken here.

13


Chapter 2

2

Computational Techniques for
Groundwater Flow Modelling


2.1

Nonlinear Techniques

As mentioned in Chapter 1, there are two popular options for solving nonlinear
systems. The first method is referred to as the Fixed Point or Picard Method, and the
second is Newton’s method. These methods aim to solve a system of nonlinear
equations of the form:
F (x ) = 0 ,

(2.1)

where F(x) represents a system of n nonlinear equations with n variables, and thus
can be considered in the form of:

14


f1 ( x1 , x 2 ,K, x n ) = 0
f 2 ( x1 , x 2 ,K, x n ) = 0
,
M
f n ( x1 , x 2 ,K, x n ) = 0

(2.2)

where the f i are known as coordinate functions. In this work it is assumed that

F : D ⊂ R N → R N where D is some convex, simply connected region contained
within the domain of the vector valued function F . Equation (2.1) defines a typical

problem that requires solution in a variety of engineering and science applications.

Before the two main methods of overcoming nonlinearity are discussed, it is
important to note that iterative methods can be grouped by their “rates of
convergence”. If we let the sequence {x (n ) } ⊂ R N and the exact solution to equation
(2.1) x * ∈ R N then the following can be stated about the rates of convergence:
1. x (n ) → x * q-quadratically if x (n ) → x * and there is a K > 0 such that:
x (n +1) − x * ≤ K x (n ) − x *

2

(2.3)

2. x (n ) → x * q-superlinearly with q-order α > 1 if x (n ) → x * and there is
K > 0 such that:
x (n +1) − x * ≤ K x (n ) − x *

α

(2.4)

3. x (n ) → x * q-linearly with q-factor σ ∈ (0,1) if:
x (n +1) − x * ≤ σ x (n ) − x *

(2.5)

for n sufficiently large.

Note that throughout this chapter unless otherwise stated, . implies 2-norm. The
above classifications are taken from [14], and are presented here for completeness

because they are mentioned in discussions concerning the nonlinear techniques
throughout this chapter. The two nonlinear techniques of interest are the Fixed Point
/ Picard and Newton methods

15