×

A parallelization technique based on factor combination and graph partitioning for general incomplete Lu factorization. (English) Zbl 1253.65168

Summary: 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.

MSC:

65N06 Finite difference methods for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations
65Y05 Parallel numerical computation
65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices

Software:

BILUM; SchurRAS; ILUT; ILUS; ILUM
PDFBibTeX XMLCite
Full Text: DOI