A BSP recursive divide and conquer algorithm to solve a tridiagonal linear system

摘要

In this paper we discuss a recursive divide and conquer method to solve a tridiagonal system of linear equations. We propose two divide and conquer algorithms using different communication schemes. The first one uses a fan-in scheme to perform communication among processors, while the second one follows a rather different model, in which all the processors communicate all data to the main one. A theoretical study of the computational cost of both algorithms is developed computing theoretical times; firstly in an IBM SP2 computer with a high performance switch and Ethernet connection, and secondly in a CRAY T3D computer. We present experimental results for the IBM SP2 computer, for 2, 4, and 8 processors, comparing these results with the theoretical predicted times.