A Sine Transform Algorithm for the Hypercube
A new sine transform algorithm is presented where the pre-and post-processing steps are amenable to implementation on the hypercube parallel computer. Interprocessor communication is minimized at the expense of some redundant computations resulting in an algorithm with almost linear speedup against the conventional sequential algorithm. The transforms for both naturally ordered input and bit-reversed input can be processed, thereby avoiding the communication overhead needed to either run an autosort algorithm or to unscramble the results by performing a bit-reversed permutation about $O(d)$ parallel transmissions on hypercubes of dimension $d$.
computer science; technical report
Previously Published As