Renumbering strategies based on multi-level techniques combined with ILU-decompositions

In this paper we present an incomplete factorization technique which uses a renumbering of the unknowns, based on a sequence of grids as in multi-grid. For many problems discretised on structured grids, we obtain almost grid-independent convergence when this factorization is combined with some conjugate gradient-like method. Also, a similar preconditioning technique is described which can be used for matrices with arbitrary sparsity patterns as those arising from finite element methods on unstructured grids. During the factorization we use a reordering to guarantee that the diagonal blocks to be inverted remain strongly diagonally dominant. This makes it possible to approximate the needed inverses by only a diagonal matrix, leading to more potential parallelism. The method is demonstrated for a number of test problems and compared to some standard methods.