Introduction#

The rocFFT library is an implementation of the discrete Fast Fourier Transform (FFT) written in HIP for GPU devices. The code is open and hosted here: ROCmSoftwarePlatform/rocFFT

The rocFFT library provides a fast and accurate platform for calculating discrete FFTs. It supports the following features:

• Half (FP16), single, and double precision floating point formats

• 1D, 2D, and 3D transforms

• Computation of transforms in batches

• Real and complex FFTs

• Arbitrary lengths, with optimizations for combinations of powers of 2, 3, 5, 7, 11, 13, and 17

rocFFT also has experimental support for:

• Distributing transforms across multiple GPU devices in a single process

• Distributing transforms across multiple MPI (Message Passing Interface) processes

FFT Computation#

The FFT is an implementation of the Discrete Fourier Transform (DFT) that makes use of symmetries in the DFT definition to reduce the mathematical complexity from $O(N^2)$ to $O(N\log N)$.

What is computed by the library? Here are the formulas:

For a 1D complex DFT:

${\tilde{x}}_j=\sum _{k=0}^{n-1}{x}_k\exp \left(\pm i\frac{2\pi jk}{n}\right)\text{ for }j=0,1,\dots ,n-1$

Where, $x_k$ are the complex data to be transformed, ${\tilde{x}}_j$ are the transformed data, and the sign $\pm$ determines the direction of the transform: $-$ for forward and $+$ for backward.

For a 2D complex DFT:

${\tilde{x}}_{jk}=\sum _{q=0}^{m-1}\sum _{r=0}^{n-1}{x}_{rq}\exp \left(\pm i\frac{2\pi jr}{n}\right)\exp \left(\pm i\frac{2\pi kq}{m}\right)$

For $j=0,1,\dots ,n-1\text{ and }k=0,1,\dots ,m-1$, where, $x_{rq}$ are the complex data to be transformed, ${\tilde{x}}_{jk}$ are the transformed data, and the sign $\pm$ determines the direction of the transform.

For a 3D complex DFT:

${\tilde{x}}_{jkl}=\sum _{s=0}^{p-1}\sum _{q=0}^{m-1}\sum _{r=0}^{n-1}{x}_{rqs}\exp \left(\pm i\frac{2\pi jr}{n}\right)\exp \left(\pm i\frac{2\pi kq}{m}\right)\exp \left(\pm i\frac{2\pi ls}{p}\right)$

For $j=0,1,\dots ,n-1\text{ and }k=0,1,\dots ,m-1\text{ and }l=0,1,\dots ,p-1$, where $x_{rqs}$ are the complex data to be transformed, ${\tilde{x}}_{jkl}$ are the transformed data, and the sign $\pm$ determines the direction of the transform.