区域分解型并行预条件的一种粗网格校正算法

A COARSE GRID CORRECTION ALGORITHM FOR DOMAIN DECOMPOSITION BASED PARALLEL PRECONDITIONERS

区域分解是并行计算的基本手段之一,在稀疏线性方程组迭代求解时,对不完全分解等串行计算时很有效的预条件,经常采用区域分解的思想进行并行化。但区域分解的本质是利用局部解来近似全局解,从而必然存在较大误差,为此,提出一种粗网格校正算法,通过非重叠子区域浓缩,每个非重叠子区域浓缩为一个超结点,形成一个含全局信息且阶数等于子区域个数的小线性方程组,之后用其对原并行预条件进行校正。对块Jacobi型、经典加性Schwarz、以及因子组合型并行不完全分解预条件的实验表明,粗网格校正能有效改善收敛性并提高求解效率。

Domaindecomposition is one of the fundamental methods for parallel computing. During the solution of sparse linear systems with iterations, for the effective preconditioners in serial computation such as incomplete factorisation, it is usual to adopt the domain decomposition ideas to parallelise. But the essence of the domain decomposition is to approximate the global solution with local solutions, which must lead to significant errors. To reduce this error, a coarse grid correction algorithm is presented through the contraction of the non-overlapped sub-domains in this paper, with each sub-domain concentrating to a super node. A small linear system with small order is formed in this way, which contains the global information, and the order is equal to the number of domains. Then, the coarse grid operator is used to correct the original parallel preconditioners. Numerical experiments with block Jacobi-type, classical additive Schwarz, and factors combination-based parallel incomplete factorisation show that the provided coarse grid correction can improve the convergence effectively, thus improves the efficiency of the solution process.