The computational of the fast Fourier transforms (FFTs) is the cornerstone of many supercomputer applications. These include not only the predictable digital signal processing, speech recognition, image processing, and petroleum seismic analysis, but also other less obvious applications, such as in computational fluid dynamics, medical technology, multiple precision arithmetic and computational number theory. Computations worthy of a parallel computer generally fall into four categories: (1) one or a few very long 1-D FFTs; (2) many small or moderate-sized 1-D FFTs; (3) one or a few large 2-D FFTs; or (4) one or a few large 3-D FFTs. The PARKBENCH \ suite includes two FFT test kernels, one for a large 1-D FFT, and one for a large 3-D FFT.
No restriction is placed on the FFT technique used to perform this convolution, except that it be based on a complex-number FFT rather than, for example, a number-theoretic FFT. It is expected, however, that efficient implementations will employ techniques, such as Edson's algorithm and real-to-complex FFTs, that take advantage of the purely real nature of the input and output data to reduce the computational cost. The usage of vendor-supplied library FFT routines is permitted. The serial implementation program includes a reasonably efficient 1-D FFT suitable for computation on a workstation or single processor vector system.
Consider the partial differential equation (PDE)
where x is a position in three-dimensional space. When a Fourier transform is applied to each side, this equation becomes
where v(z,t) is the Fourier transform of u(x,t). This has the solution
In this benchmark a 3-D complex array U, which represents u is first filled with pseudorandom data generated by the same scheme as used in the embarrassingly parallel kernel. Then we compute V, the result of a forward 3-D FFT of U. For each of several iterations, V is multiplied by the appropriate exponential factors and performs an inverse 3-D FFT on the result.
Any complex FFT algorithm may be used for the computation of the 3-D FFTs mentioned above, and vendor-supplied library routines may be employed.