GPU-Accelerated Incomplete Cholesky Factorization Preconditioned Conjugate Gradient Method

Incomplete Cholesky factorization preconditioned conjugate gradient (ICCG) method is effective to solve large sparse symmetric positive definite linear systems. However, ICCG method requires solving two sparse triangular linear systems during each iteration. The inherent serialism of solving sparse triangular becomes a bottleneck which prevents high efficient parallelization of ICCG method on GPU platform. In this paper, an effective method to accelerate solving sparse triangular on GPU platform is proposed. In order to increase the multi-thread parallelism of solving sparse triangular on GPU platform, level scheduling is exploited for the sparse triangular matrixes which incomplete Cholesky factorization generates. For further improving the parallel performance of solving sparse triangular, approximate minimum degree (AMD) algorithm is used to reorder the coefficient matrix before level scheduling. Moreover, a novel method, taking advantage of the level information to reorder the sparse triangular matrices after level scheduling, is applied. These two methods can decrease the number of levels during level scheduling and optimize GPU memory access pattern to utilize memory coalescing in solving sparse triangular, respectively. Numerical experiments indicate that compared with ICCG method implemented with NVIDIA CUSPARSE, applying the above methods can obtain more than 100% performance improvement on average.