Gray codes, fast Fourier transforms and hypercubes

DOI10.1016/0167-8191(88)90087-7MaRDI QIDQ1097676zbMATH OpenOpenAlexFDO

Authors R. M. Chamberlain

Publication date 1988

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(88)90087-7

zbMATH Keywords

fast Fourier transformGray codehypercube architectureparallel processing

Mathematics Subject Classification ID

Trigonometric interpolation (42A15) Numerical methods for trigonometric approximation and interpolation (65T40) Parallel numerical computation (65Y05)

Review text

The usefulness of the hypercube architecture is stressed for the implementation of the fast Fourier transform. It is so because the data communications at every step of computation are only needed between neighbouring processors. If the data are distributed according to a binary reflected Gray code, the computing time increases a little as an effect due to imbalance in the load between processors.

Recommendations

• An efficient algorithm for gray-to-binary permutation on hypercubes
• A comparison of optimal FFTs on torus and hypercube multicomputers
• scientific article; zbMATH DE number 800360
• Two-dimensional FFT algorithms on hypercube and mesh machines
• Cooley-Tukey FFT on the Connection Machine

Cited in

(12)

• FFT algorithms and their adaptation to parallel processing
• Resource allocation strategies for hypercube architectures
• Product-shuffle networks: Toward reconciling shuffles and butterflies
• On constructing multiple spanning trees in a hypercube
• An efficient algorithm for gray-to-binary permutation on hypercubes
• Fault-tolerant algorithm for Fast Fourier Transform on hypercubes
• Gray codes for reflection groups
• A new parallel strategy for two-dimensional incompressible flow simulations using pseudo-spectral methods
• Optimal embeddings of butterfly-like graphs in the hypercube
• Efficient Computation of Middle Levels Gray Codes
• Pseudospectral methods on massively parallel computers
• The parallel Fourier pseudospectral method

This page was built for publication: Gray codes, fast Fourier transforms and hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097676)