Iterative Solution of Saddle Point Problems with Applications to Groundwater Flow

Project Description

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 elements.


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 DOUG code.

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.

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 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.

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).

Acknowldegment 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).

[Home] [Department of Mathematical Sciences] [University of Bath]

Last updated 03/04/2002