Solving Tridiagonal Linear Systems On the Butterfly Parallel Computer

Abstract

A parallel block partitioning method to solve a tri diagonal system of linear equations is adapted to the BBN Butterfly multiprocessor. A performance analysis of the programming experiments on the 32-node Butterfly is presented. An upper bound on the number of pro cessors to achieve the best performance with this method is derived. The computational results verify the theoretical speedup and efficiency results of the parallel algorithm over its serial counterpart. Also included is a study comparing performance runs of the same code on the Butterfly processor with a hardware floating point unit and on one with a software floating point facility. The total parallel time of the given code is considerably reduced by making use of the hardware floating point facility whereas the speedup and efficiency of the par allel program considerably improve on the system with software floating point capability. The achieved results are shown to be within 82% to 90% of the predicted performance.