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

计算物理 ›› 2008, Vol. 25 ›› Issue (6): 673-682.

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

吴建平¹, 宋君强², 李晓梅²

1. 国防科技大学计算机学院, 湖南长沙 410073;
2. 装备指挥技术学院, 北京 101416

收稿日期:2007-06-25 修回日期:2007-11-26 出版日期:2008-11-25 发布日期:2008-11-25
作者简介:吴建平(1974-),男,博士,副研究员,主要从事科学计算与并行算法方面的研究.
基金资助:
计算物理重点实验室基金;并行与分布处理重点实验室基金;国家自然科学基金(10505030,40505023)资助项目

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

WU Jianping¹, SONG Junqiang², LI Xiaomei²

1. School of Computer Science, National University of Defense Technology, Changsha 410073, China;
2. Institute of Command and Technology of Equipment, Beijing 101416, China

Received:2007-06-25 Revised:2007-11-26 Online:2008-11-25 Published:2008-11-25

摘要/Abstract

摘要： 对块三对角线性方程组,不完全分解是最有效的预条件之一,但它本质上是一个串行计算过程,难以有效并行化.基于一维重叠区域分解,对局部不完全分解得到的上、下三角因子分别各自进行组合,构造一类全局的并行不完全分解型预条件.在具体实现时,给出两种具体途径,其中一种基于所有重叠部分对应分量的交换.之后,在仔细对其中的计算过程进行分析的基础上,给出一种只需要一条网格线上分量通信的实现算法,大大减少了通信量,且通信不随重叠度的增加而增加.这种并行化方法可以应用于块三对角线性方程组的任何不完全分解型预条件.实验结果表明,文中提出的并行化方法普遍优于加性Schwarz并行化方法.

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

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

Key words: solution of linear systems, block tridiagonal matrix, incomplete factorization, additive Schwarz, parallel algorithm

中图分类号:

O242

吴建平, 宋君强, 李晓梅. 块三对角线性方程组不完全分解预条件的一种一维区域分解并行化方法[J]. 计算物理, 2008, 25(6): 673-682.

WU Jianping, SONG Junqiang, LI Xiaomei. Parallelization of Incomplete Factorization Preconditioning of Block Tridiagonal Linear Systems with 1-D Domain Decomposition[J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2008, 25(6): 673-682.

[1]	胡晓燕, 范征锋. 惯性约束聚变内爆中基于多块结构网格的高效辐射扩散并行算法[J]. 计算物理, 2022, 39(3): 277-285.
[2]	朱家莉, 尚月强. 不可压缩流的并行两水平稳定有限元算法[J]. 计算物理, 2022, 39(3): 309-317.
[3]	蔡颖, 张存波, 刘旭, 范征锋, 刘元元, 徐小文, 张爱清. 二维球坐标系中子输运方程的一种并行SN算法[J]. 计算物理, 2022, 39(2): 143-152.
[4]	丁琪, 尚月强. 非定常Navier-Stokes方程基于两重网格离散的有限元并行算法[J]. 计算物理, 2020, 37(1): 10-18.
[5]	张守慧, 梁栋. 二维抛物型问题的Strang型交替分段区域分裂格式[J]. 计算物理, 2018, 35(4): 413-428.
[6]	祁美玲, 杨琼, 王苍龙, 田园, 杨磊. 结构材料辐照损伤的分子动力学程序GPU并行化及优化[J]. 计算物理, 2017, 34(4): 461-467.
[7]	尚月强, 何银年. 非定常Navier-Stokes方程基于完全重叠型区域分解的有限元并行算法[J]. 计算物理, 2011, 28(2): 181-187.
[8]	张守慧, 王文洽. 对流扩散问题的高精度交替组分八点格式[J]. 计算物理, 2009, 26(5): 703-711.
[9]	吴建平, 宋君强, 张卫民, 李晓梅. 块三对角线性方程组的一类二维区域分解并行不完全分解预条件[J]. 计算物理, 2009, 26(2): 191-199.
[10]	周春华. 流动数值模拟中一种并行自适应有限元算法[J]. 计算物理, 2006, 23(4): 412-418.
[11]	郭晓虎, 张林波. 求解可压Navier-Stokes方程的对称超紧致差分格式及其并行算法[J]. 计算物理, 2006, 23(3): 281-289.
[12]	刘青凯, 张林波. 一种分布式内存环境下的并行二分网格加密算法[J]. 计算物理, 2005, 22(5): 399-406.
[13]	冉瑞生, 黄廷祝, 冷劲松. 一类块三对角矩阵求逆的算法[J]. 计算物理, 2005, 22(5): 412-416.
[14]	吴建平, 李晓梅. 三维问题的局部块分解预条件[J]. 计算物理, 2003, 20(1): 76-80.
[15]	张宝琳, 陆金甫, 陶应学, 杜正平. 非线性热传导方程的分组隐式解法及数值结果[J]. 计算物理, 2002, 19(1): 8-12.