Part II Numerical Mathematics
Towards a cost-effective ILU preconditioner with high level fill
E. F. D'Azevedo1, P. A. Forsyth2 and Wei-Pai Tang2
| (1) | Mathematical Sciences Section, Oak Ridge National Laboratory, 37831 Oak Ridge, Tennessee, USA |
| (2) | Department of Computer Science, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada |
Received: 15 December 1990 Revised: 15 October 1991
Abstract There has been increased interest in the effect of the ordering of the unknowns on Preconditioned Conjugate Gradient (
PCG) methods. A recently proposed Minimum Discarded Fill (
MDF) ordering technique is effective in finding good
ILU(
l) preconditioners, especially for problems arising from unstructured finite element grids. This algorithm can identify anisotropy in complicated physical structures and orders the unknowns in an appropriate direction. The
MDF technique may be viewed as an analogue of the minimum deficiency algorithm in sparse matrix technology, and hence is expensive to compute for high level
ILU(
l) preconditioners.
In this work, several less expensive variants of theMDF technique are explored to produce cost-effectiveILU preconditioners. The ThresholdMDF ordering combinesMDF ideas with drop tolerance techniques to identify the sparsity pattern in theILU preconditioners. The Minimum Update Matrix (MUM) ordering technique is a simplification of theMDF ordering and is an analogue of the minimum degree algorithm. TheMUM ordering method is especially effective for large matrices arising from Navier-Stokes problems.
AMS(MOS) subject classifications 65F10 - 76S05
Key words Minimum discarded fill (MDF) - thresholdMDF
- minimum updating matrix - matrix ordering - preconditioned conjugate gradient
This work was supported by the Natural Sciences and Engineering Research Council of Canada, by the Information Technology Research Centre, which is funded by the Province of Ontario, and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc., through an appointment to the U.S. Department of Energy Postgraduate Research Program administered by Oak Ridge Associated Universities.
References secured to subscribers.