ORDERING METHODS FOR PRECONDITIONED CONJUGATE-GRADIENT METHODS APPLIED TO UNSTRUCTURED GRID PROBLEMS

It is well known that the ordering of the unknowns can have a significant effect on the convergence of preconditioned conjugate gradient (PCG) methods. There has been considerable experimental work on the effects of ordering for finite difference problems. In many cases, good results have been obtained with preconditioners based on diagonal, spiral, red/black reduced system orderings, or some others. The reduced system approach generally gives rapid convergence. There has been comparatively less work on the effect of ordering for finite element problems on unstructured meshes. In this paper, an ordering technique for unstructured grid problems is developed. At any stage of the partial elimination, the next pivot node is selected so as to minimize the norm of the discarded fill matrix. Numerical results are given for model problems and for problems arising in groundwater contamination. Computations are reported for two-dimensional triangular grids, and for three-dimensional tetrahedral grids. The examples show that ordering is important even if a reduced system (based on a generalized red/black ordering) method is used.