An overlapped two-way method for solving tridiagonal linear systems in a BSP computer

In this paper we present a new overlapped two-way parallel method for solving tridiagonal linear systems on a bulk-synchronous parallel (BSP) computer. We develop a theoretical study of the computational cost for this new method and we compare it with the experimental times measured on an IBM SP2 using switch hardware for the communications between processors. Using the cost model, we also obtain theoretical results on a CRAY T3E and we achieve a study on the optimum number of processors.