TOWARDS A COST-EFFECTIVE ILU PRECONDITIONER WITH HIGH-LEVEL FILL

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 the MDF technique are explored to produce cost-effective ILU preconditioners. The Threshold MDF ordering combines MDF ideas with drop tolerance techniques to identify the sparsity pattern in the ILU preconditioners. The Minimum Update Matrix (MUM) ordering technique is a simplification of the MDF ordering and is an analogue of the minimum degree algorithm. The MUM ordering method is especially effective for large matrices arising from Navier-Stokes problems.