Parallel ILU (k) preconditioner implementation and performance analysis

Large-scale linear systems are encountered in many scientific computing fields such as the petroleum, finance, biology etc. The acceleration of solving these systems is crucial for advanced researches. A preconditioner is the... [ view full abstract ]

Large-scale linear systems are encountered in many scientific computing fields such as the petroleum, finance, biology etc. The acceleration of solving these systems is crucial for advanced researches. A preconditioner is the core technique for improving the robustness and efficiency of iterative solvers. We devoted our efforts to investigate the principle and parallel implementation of ILU (k) preconditioner which is commonly used.

Differing from ILU (0), ILU (k) uses the k level to control the pattern of a preconditioner matrix. We developed the ILU (k) in a decoupled way which separates the symbolic phase and the factorization phase. In order to improve the parallel structure of preconditioner systems, the domain partition (RAS) is applied on the original matrix first. The ILU (k) is then used on each sub matrix. The final task focuses on the solution of the lower triangular system and the upper triangular system. We developed the parallel triangular solver based on the level schedule method to solve them. Therefore, the entire preconditioner solution phase can be completed in parallel.

As the domain partition provides high parallel performance by losing calculation accuracy, the number of domains is a key factor to control the performance. Coupling with the level k of ILU (k), a complex situation appears in the parallel solution process. We implemented the entire algorithm on NVIDIA GPUs to illustrate this phenomenon. Favorable efficiency of the ILU (k) preconditioner is verified by this implementation. Parallel characteristics of the ILU (k) algorithms are also detailed stated.