块三对角线性方程组的重叠分割可扩展并行近似求解方法

上海大学学报(自然科学版)

块三对角线性方程组的重叠分割可扩展并行近似求解方法

张衡1，2，张武1，封卫兵1

1.上海大学计算机工程与科学学院，上海 200072；2.石河子大学师范学院数学系，石河子 832000

收稿日期:2006-06-29 修回日期:1900-01-01 出版日期:2007-04-30 发布日期:2007-04-30
通讯作者: 张衡

Approximate Parallel Solution to System of Block Tri-diagonalLinear Equations with Overlapped Partition Algorithm

ZHANG Heng1,2,ZHANG Wu1,FENG Wei-bing1

1. School of Computer Engineering and Science, Shanghai University,Shanghai 200072, China;2. Department of Mathematics, Teachers College, Shihezi University, Shihezi 832000, China

Received:2006-06-29 Revised:1900-01-01 Online:2007-04-30 Published:2007-04-30
Contact: ZHANG Heng

摘要/Abstract

摘要： 基于并行计算的分治思想，对于严格块对角占优的块三对角线性方程组提出一个可扩展的块重叠分割并行近似求解方法(PBOA方法).在机器精度内，利用块对角占优的条件，只需要相邻处理器间一次通讯，得到与精确解等价的近似解.在算法设计中，充分考虑计算与通信的重叠和处理机间负载平衡.通过精度分析，给出子方程组的阶数与精度的关系，从而得到通过调整子方程组的阶数来控制精度和并行效率，保证可扩展性的方法，得到的并行计算效率可随着问题规模的增加而增加.该文的方法在上海大学并行计算机“自强3000”上运行，数值实验的结果与理论分析的结果一致，得到的并行计算效率接近67%，加速比几乎是线性的.

关键词: 矩阵分割, 块LU分解, 块对角占优, 块三对角线性方程组, 相对误差

Abstract: A high efficiency scalable parallel algorithm, parallel block overlapped partiti on approximate (PBOA) algorithm, is proposed for solving block tri-diagonal linear systems on multiple computers. The algorithm is based on the divided-and-conquer idea in parallel computation. When the system is strictly block diagonal dominant, the PBOA is highly parallel and provides an solution that equals the exact solution within machine accuracy with finite communications between adjacent processors. By analyzing the accuracy, the relation between the accuracy and the order of the system is obtained. The authors propose the method for improving efficiency and accuracy. The computation efficiency increases with size of the problem. The proposed method has been implemented on 64 nodes of the ZQ3000 parallel computer at Shanghai University. The numerical results agree with the theoret ical analysis. With desired accuracy, linear speedup has been obtained, and the parallel efficiency approaches 67%.

Key words: block diagonal dominant, block LU decomposit ion method, matrix partitioning, relative error, block tri-diagonal linear systems

中图分类号:

TP 301.6

张衡;张武;封卫兵. 块三对角线性方程组的重叠分割可扩展并行近似求解方法[J]. 上海大学学报(自然科学版).

ZHANG Heng;ZHANG Wu;FENG Wei-bing. Approximate Parallel Solution to System of Block Tri-diagonalLinear Equations with Overlapped Partition Algorithm [J]. Journal of Shanghai University（Natural Science Edition）.