A Novel Multicolor Ordering Method for GPU Acceleration of ILU(0)-GMRES

Abstract. The ILU(0) preconditioner is widely used to improve the convergence of Krylov subspace methods. However, it typically requires triangular solves with strong data dependencies, limiting the efficiency of parallel execution on graphical processing units (GPUs), for which high concurrency is critical. Matrix reordering can increase concurrency in triangular solves, but conventional reordering methods may eliminate data dependencies that are essential for maintaining the preconditioning effectiveness of ILU(0). To address this, we consider two reordering methods: our previously proposed hierarchical block multicolor (HBMC) ordering and its new variant, two-step multicolor (TMC) ordering. Both methods exploit block structures to preserve significant data dependencies while improving concurrency. We also develop efficient GPU implementations of triangular solves under these reordering methods. Numerical experiments on NVIDIA V100 and A100 GPUs using the ILU(0)-preconditioned flexible generalized minimal residual (GMRES) solver show that HBMC and TMC outperform the conventional multicolor ordering technique in both convergence speed and overall solver performance.