Comparison Criteria for Parallel Orderings in ILU Preconditioning

This paper introduces block red-black ordering in a general three-dimensional form for parallel incomplete LU (ILU) preconditioning. This parallel ordering method is designed to attain fast convergence with reduced synchronization among processors in parallelized forward and backward substitutions. In this method, the grid-nodes are divided into blocks and red-black ordering is applied to them. Since blocks with identical colors never have a data-dependency, the blocks in each color can be processed in parallel. Moreover, in order to compare parallel orderings, we propose a new tool for investigating orderings on convergence. The analytic index for convergence, which is based on the remainder matrix, is easily computed and has a unique value for a fixed ordering. Nodes are classified into seven groups, and the effect of each group on convergence is estimated. Numerical tests using a three-dimensional problem confirm the validity of both proposed parallel ordering and analytic convergence comparison methods.