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

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

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

A high efficiency scalable parallel algorithm,parallel block overlapped partition 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 theoretical analysis.With desired accuracy,linear speedup has been obtained,and the parallel efficiency approaches 67%.