AN EFFECTIVE PARALLEL ALGORITHM FOR SOLVING TRIDIAGONAL LINEAR SYSTEMS ON DISTRIBUTED MEMORY MULTICOMPUTERS

A parallel algorithm for solving tridiagonal linear systems on distributed memory multicomputers is presented. The algorithm is based on the divide and conquer principle. The reduction system is formed and solved efficiently. The unnecessary redundancy computation is avoided. On account of carefully estimating the computation task, the loads of solving the system are evenly distributed among the processors. This algorithm makes full use of overlapping between computation and communication to decreas the amount of processors’ idle time. The complexity of the algorithm is analyzed. The results of numerical experiments about the algorithm on a multicomputer are presented. The numerical results show that the efficiency of this algorithm is much higher than that of Chi Li hua and Li Xiao mei’s DPP algorithm.