A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors (Q1822894)

The authors give a limited processor version of the recursive doubling algorithm for the solution of tridiagonal linear systems using parallel arithmetic steps on a parallel computer. They make use of fast parallel prefix algorithms. The algorithm achieves linear speedup and constant efficiency over its sequential implementation. Computational results are given based on an Intel iPSC/d5 hypercube multiprocessor. The authors are in the process of extending the proposed algorithm to general recurrence relations, block tridiagonal and banded linear systems.