块对角占优块三对角方程组的块重叠分割无通信并行求解方法

A Parallel Block Overlapped Partition Un-communication Algorithm for Block Diagonal Dominant Block Tri-diagonal Systems

基于并行计算的分治思想,对块三对角线性方程组的求解提出了一个块重叠分割无通信的高效可扩展并行算法(PBOPUC算法)。当系统严格块对角占优时,在机器精度内,得到与精确解等价的近似解。通过精度分析,得到子方程组的阶数与精度的关系,并用它来控制精度和并行效率。本文的算法已经在上海大学的高性能并行计算机"自强3000"上实现,结果说明,并行计算效率接近100%,加速比几乎是线性的。

A highly efficient scalable parallel algorithm, named parallel block overlapped partition uncommunication （PBOPUC） algorithm, is proposed for solving block tri-diagonal linear systems. The algorithm is based on the divide-and-conquer idea in parallel computing. For strict block diagonal dominant systems, the PBOPUC provides an approximate solution that equals to the exact solution within machine accuracy. By accuracy analysis, the relations between accuracy and orders of subsystems are obtained, which can be used to control accuracy and improve parallel efficiency. This algorithm has been implemented on ZQ3000 high performance parallel computer in Shanghai University. The results show that the parallel efficiency is nearly 100%, while the speedup is almost linear.