块三对角线性方程组不完全分解预条件的一种一维区域分解并行化方法  

Parallelization of Incomplete Factorization Preconditioning of Block Tridiagonal Linear Systems with 1-D Domain Decomposition

作　　者：吴建平[1] 宋君强[1] 李晓梅[2] 

机构地区：[1]国防科技大学计算机学院,湖南长沙410073 [2]装备指挥技术学院,北京101416

出　　处：《计算物理》2008年第6期673-682,共10页Chinese Journal of Computational Physics

基　　金：计算物理重点实验室基金;并行与分布处理重点实验室基金;国家自然科学基金(10505030,40505023)资助项目

摘　　要：对块三对角线性方程组,不完全分解是最有效的预条件之一,但它本质上是一个串行计算过程,难以有效并行化.基于一维重叠区域分解,对局部不完全分解得到的上、下三角因子分别各自进行组合,构造一类全局的并行不完全分解型预条件.在具体实现时,给出两种具体途径,其中一种基于所有重叠部分对应分量的交换.之后,在仔细对其中的计算过程进行分析的基础上,给出一种只需要一条网格线上分量通信的实现算法,大大减少了通信量,且通信不随重叠度的增加而增加.这种并行化方法可以应用于块三对角线性方程组的任何不完全分解型预条件.实验结果表明,文中提出的并行化方法普遍优于加性Schwarz并行化方法.Based on one-dimensional domain decomposition with small overlapping, we approximate local lower and upper triangular incomplete factors and combine these factors into an effective approximation for global incomplete factorization preconditioner of coefficient matrix. Two implementations are considered. One is based on exchange of total boundary values of overlapped domain. The other is based on carefully arranged computation process to reduce communication of whole overlapped domain in one line of grid points. The parallelization method can be used to any incomplete factorization preconditioner. Experiments show that it is more efficient than widely-used additive Schwarz technique.

关 键 词：线性方程组求解 块三对角矩阵 不完全分解 加性Schwarz 并行算法 

分 类 号：O242[理学—计算数学]