A parallel version of the cyclic reduction algorithm on a hypercube (Q1319517)

An adaptation of the cyclic odd-even reduction algorithm to distributed memory parallel multiprocessors is presented. The original method is parallelized in such a way that independently solvable linear subsystems are obtained. As the size of each subsystem corresponds to the number of participating processors, a hypercube topology is well suited for execution of these tasks because the communication only among neighbours is required. The method has been tested by running on a parallel system consisting of 32 transputers.