A parallel algorithm to solve tridiagonal systems on distributed memory multiprocessors

The authors design and implement an efficient algorithm that uses the cyclic odd-even reduction method to solve large tridiagonal systems on a distributed memory multiprocessor. The algorithm works on a bidirectional array of transputers, and the code has been written in Occam2. The algorithm performs a parallel cyclic reduction of the original system, solves the reduced system using Gaussian elimination and obtains the remaining solutions with a cyclic backward substitution phase. They present both a theoretical and an experimental study of its performance on the Parsys SN-1000. Results reflect a real efficiency close to the theoretical maximum