Iterative Solution of Saddle Point Problems with Applications to
This project is concerned with the parallel solution of linear systems
arising from mixed finite element discretisations of two- and
three-dimensional models for groundwater flow coupled with the transport of
salinity. The project is funded by EPSRC
CASE Award 97D00023. The cooperating body,
AEA Technology , Harwell, Oxford, UK, has written and markets the code
NAMMU ("Numerical Assessment Method for Migration Underground") which is used
commercially on a range of pollution control applications.
Mathematically the project concerns the development and implementation of
parallel iterative methods for the saddle-point system arising from mixed
finite element discretisations of partial differential equations describing
groundwater flow, and in particular for the coupled system which arises when
nonlinear salinity effects are included.
Computationally it is envisaged that these methods will be implemented using
the approach of the DOUG (Domain Decomposition on Unstructured Grids) package
recently developed in Bath. Details of this package, which uses the message
passing platform MPI, are available at the
DOUG Home Page . One of
the chief initial computational tasks will be to extend it to mixed finite
In the first two years we were able to devise a robust parallel iterative
method for the two-dimensional steady state case of groundwater flow. It is
built on two essential steps. The first step is a decoupling procedure that
reduces the arising saddle-point system to a smaller symmetric positive
definite system for the velocity field and a triangular system for the
pressure, by constructing a basis for the subspace of divergence-free
Raviart-Thomas mixed finite elements. The second step is the parallel solution
of the resulting linear equation systems using the
Numerical experiments show that
this method exhibits a good degree of robustness with respect to the mesh size
and to the large discontinuities in the permeability field, which are present
in realistic flow problems. Even in the extreme case of a statistically
determined permeability field (as used in the description of highly
heterogeneous media) we can report an excellent performance of our solver.
The details of this work can be found in:
We were also able to extend the decoupling procedure (i.e. the construction
of a divergence-free basis) to three-dimensional Raviart-Thomas-Nedelec
elements on tetrahedra. The proof of existence of such a basis involves
techniques from graph theory and algebraic topology. Previously the literature
had been restricted to a paper by Hecht (RAIRO M^2AN 15, 1981) on
non-conforming P1-P0 elements for the related Stokes problem, and a paper
by Cai et al. (to appear in SIAM J Num Anal) for uniform rectangular grids.
This work was presented first at the 18th Biennial Conference on Numerical
Analysis in Dundee, 29th June - 2nd July 1999.
- K.A. Cliffe, I.G. Graham, R. Scheichl, and L. Stals,
Parallel Computation of Flow in Heterogeneous Media Modelled by Mixed
Finite Elements. Journal of Computational Physics
The details of this work can be found in the following paper:
which was selected as one of the SIAM Student Paper Prize
winners, awarded at the
SIAM Annual Meeting in Puerto Rico, 10th - 14th July 2000, and
in my PhD thesis
- R. Scheichl,
Decoupling Three-dimensional Mixed Problems Using
Divergence-free Finite Elements. (SIAM Student Paper Prize 2000)
SIAM Journal of Scientific Computing 23 (5):1752-1776, 2002.
Future work will involve the construction of a parallel
preconditioner for the resulting symmetric positive definite problem
for 3D, as done in 2D. Since the constructed basis can be interpreted
in the framework of the Nedelec edge-elements, we are interested
in/looking at preconditioners developed for those elements,
especially in the context of Maxwell's equations.
This link between Nedelec edge-elements for Maxwell's equations and
divergence-free Raviart-Thomas-Nedelec (face-)elements has only recently been
pointed out/investigated by several research groups (Boffi, Brezzi; Hiptmair,
Hoppe; Toselli, Widlund; ...), and any results found in this project will also
be of interest to people solving Maxwell's equations.
- R. Scheichl,
Iterative Solution of Saddle Point Problems Using Divergence-free
Finite Elements with Applications to Groundwater Flow. PhD
Thesis, University of Bath, 2000.
[PostScript file (without large colour pictures)]
Additionally we are also working at the moment on a different
approach to the above decoupling strategy which aims at using a
variant of the block-preconditioned Minimal Residual
(MINRES) method developed by Rusten and Winther (SIAM J Matrix
Anal. Appl. 13, 1992).
I would like to thank Prof. A. Swann for helping me
with the algebraic topology and Prof. T. Russell for kindly sending us a copy
of an unpublished manuscript by F. Hecht (1988).
[Department of Mathematical Sciences]
[University of Bath]
Last updated 03/04/2002