Two and three dimensional FFTs on highly parallel computers

DOI10.1016/0167-8191(86)90033-5MaRDI QIDQ1819919zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andrew Brass, G. Stuart Pawley

Publication date 1986

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(86)90033-5

zbMATH Keywords

distributed array processorfast Fourier transformparallel processingSIMD architecturethree-dimensional Fourier transformtwo-dimensional Fourier transform

Mathematics Subject Classification ID

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

Review text

Suppose an algorithm is available for a 2-d Fourier transform (FT) on a set of \(N^ 2_ p\) data points where \(N^ 2_ p\) is the number of processing elements. Using this routine and an interleaving technique an algorithm is derived for computing 2-d FTs on a set of \(N^ 2\) data points on computers of SIMD architecture where \(N_ p/N\) is a power of two. 3-d FTs on a set of \(N^ 3\) complex data points are calculated utilizing the 2-d results and the 1-d N-point transform for the third dimension which is computed using a base \('r_ 1+r_ 2'\) fast FT where \(N=r_ 1r_ 2\). A general program is described to calculate 3-d FTs for any values of N and \(N_ p\) where \(N_ p/N\) is a power of two including timings for the runs on an ICL distributed array processor.

Recommendations

• A PARALLEL FAST FOURIER TRANSFORM
• Two-dimensional FFT algorithms on hypercube and mesh machines
• scientific article; zbMATH DE number 3997125
• scientific article; zbMATH DE number 991433
• FAST FOURIER TRANSFORM ALGORITHM DESIGN AND TRADEOFFS ON THE CM-2

Cited in

(22)

• The efficiency of application of dual-processor computers for the analysis of the three-dimensional second harmonic generation problem
• An algorithm for distributed computation of FFTs
• Banyan models for the parallel implementation of the fast Fourier transform algorithm
• Efficient implementation of multidimensional fast Fourier transforms on a Cray X-MP
• 2-D FFT algorithm by matrix factorization in a 2-D space
• Parallel 3-dim fast Fourier transforms with load balancing of the plane waves
• Two-dimensional FFT algorithms on hypercube and mesh machines
• A distributed memory algorithm for 3-D FFTs
• Rotating a three-dimensional array in an optimal position for vector processing: Case study for a three-dimensional fast Fourier transform
• High-performance radix-2, 3 and 5 parallel 1-D complex FFT algorithms for distributed-memory parallel computers
• The six-step algorithm for two-dimensional FFTs
• Parallel three-dimensional nonequispaced fast Fourier transforms and their application to particle simulation
• Programming the WFTA for two-dimensional data
• P3DFFT: A framework for parallel computations of Fourier transforms in three dimensions
• scientific article; zbMATH DE number 123335 (Why is no real title available?)
• scientific article; zbMATH DE number 4126681 (Why is no real title available?)
• Efficient 2D FFT implementation on mediaprocessors
• Two- and three-dimensional image rotation using the FFT
• An Implementation of Multiple and Multivariate Fourier Transforms on Vector Processors
• scientific article; zbMATH DE number 820533 (Why is no real title available?)
• scientific article; zbMATH DE number 833642 (Why is no real title available?)
• Performance of the 3D FFT on the 6D network torus QCDOC parallel supercomputer

This page was built for publication: Two and three dimensional FFTs on highly parallel computers

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