A BSP Recursive Divide and Conquer Algorithm to Compute the Inverse of a Tridiagonal Matrix

In this paper we discuss a recursive divide and conquer algorithm to compute the inverse of an unreduced tridiagonal matrix. It is based on the recursive application of the Sherman–Morrison formula to a diagonally dominant tridiagonal matrix to avoid numerical stability problems. A theoretical study of the computational cost of this method is developed, comparing it with the experimental times measured on an IBM SP2 using switch and Ethernet hardware for communications between processors. Experimental results are presented for two and four processors. Finally, the method is compared with a divide and conquer method for solving tridiagonal linear systems.