Optimal Embeddings of the FFT Graph in the Hypercube
David S. Greenberg, Lenwood S. Heath, Arnold L. Rosenberg · 1988
WE PRESENT TWO LINEAR-TIME ALGORITHMS FOR EMBEDDING THE N-LEVEL `FFT'' GRAPH, WHICH HAS (N + 1)2(SUPERSCRIPT N) VERTICES, IN THE (N + [LOG(N + 1)])-DIMENSIONAL HYPERCUBE, WITH UNIT DILATION. THUS, THE `FFT'' GRAPH IS BIG ENOUGH TO HOLD IT. THE SIMPLER OF OUR ALGORITHMS USES GRAY CODES TO PERFORM THE EMBEDDING; THE MORE COMPLICATED HAS THE ADVANTAGE OF BEING MODULAR. EITHER EMBEDDING YIELDS A MAPPING OF THE `FFT'' ALGORITHM ONTO THE HYPERCUBE ARCHITECTURE, WITH UNIT (HENCE, OPTIMAL) DILATION AND OPTIMAL EXPANSION.