A Parallelization Technique Based on Factor Combination and Graph Partitioning for General Incomplete LU Factorization
Jian Ping Wu, Jun Zhao, Jun Qiang Song, Xiao Mei Li · SIAM Journal on Scientific Computing · 2012
We present a new parallelization scheme based on factor combination for general incomplete LU factorization. In this scheme, overlapped domain decomposition based on adjacent graphs is applied, and a sequence of overlapped subgraphs is formed. For each subgraph, any kind of incomplete LU factorization can be applied. The overall parallel preconditioner is then constructed as the product of the overall upper and lower triangular factors, which are derived from the combination of local factors with the idea of restricted additive Schwarz. In the solution of auxiliary linear systems related to the preconditioner, the overall factors are formed implicitly to reduce the computational cost. The analyses show that the new scheme is more effective than classical additive Schwarz and restricted additive Schwarz. When local preconditioners are symmetric positive definite, the derived parallel version preserves the property, which is vital to the conjugate gradient iterations. Finally, the new technique is tested in solving linear systems from the model two-dimensional (2D) and three-dimensional (3D) partial differential equations with finite differences and those from mesoscale numerical simulation of concrete. The results show that it is usually superior to classical additive Schwarz and block Jacobi. For nonsymmetric cases, it is also comparable to restricted additive Schwarz.