Parallel power-of-two FFTs on hypercubes

Mahn ling Woo, Rosemary Renaut

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Theoretical analysis of ordered power-of-two fast Fourier transforms (PO2FFTs) demonstrates that the most efficient algorithms for hypercube architectures may not always use nearest-neighbor communication. It is shown that an ordered PO2FFT can be obtained with just d interprocessor communications for any r if the restriction that all communications are distance one is removed. The two interprocessor communications requirements of this algorithm are determined. Packets of size N/2d+1 are transmitted in both of the ordered PO2FFT algorithms. The time complexity of both the distance one and the distance two algorithms is discussed.

Original languageEnglish (US)
Title of host publicationProc Supercomput 91
PublisherPubl by IEEE
Number of pages10
ISBN (Print)0818621583, 9780818621581
StatePublished - 1991
EventProceedings of Supercomputing '91 - Albuquerque, NM, USA
Duration: Nov 18 1991Nov 22 1991

Publication series

NameProc Supercomput 91


OtherProceedings of Supercomputing '91
CityAlbuquerque, NM, USA

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Parallel power-of-two FFTs on hypercubes'. Together they form a unique fingerprint.

Cite this