A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors
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.
scientific article; zbMATH DE number 4113847
scientific article