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