1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
.. meta::
:description: rocFFT computations
:keywords: rocFFT, ROCm, API, documentation, install, computation, fft
.. _fft-computation:
********************************************************************
FFT computation
********************************************************************
rocFFT is an implementation of the Discrete Fourier Transform (DFT) that makes use of symmetries in the DFT definition to
reduce the mathematical complexity from :math:`O(N^2)` to :math:`O(N \log N)`.
How does the library compute DFTs?
==================================
Here are the formulas for 1D, 2D, and 3D complex DFTs:
For a 1D complex DFT:
:math:`{\tilde{x}}_j = \sum_{k=0}^{n-1}x_k\exp\left({\pm i}{{2\pi jk}\over{n}}\right)\hbox{ for } j=0,1,\ldots,n-1`
Where :math:`x_k` is the complex data to be transformed, :math:`\tilde{x}_j` is the transformed data,
and the sign :math:`\pm`
determines the direction of the transform: :math:`-` for forward and :math:`+` for backward.
For a 2D complex DFT:
:math:`{\tilde{x}}_{jk} = \sum_{q=0}^{m-1}\sum_{r=0}^{n-1}x_{rq}\exp\left({\pm i} {{2\pi jr}\over{n}}\right)\exp\left({\pm i}{{2\pi kq}\over{m}}\right)`
For :math:`j=0,1,\ldots,n-1\hbox{ and } k=0,1,\ldots,m-1`, where :math:`x_{rq}` is the complex data to be transformed,
:math:`\tilde{x}_{jk}` is the transformed data, and the sign :math:`\pm` determines the direction of the transform.
For a 3D complex DFT:
:math:`\tilde{x}_{jkl} = \sum_{s=0}^{p-1}\sum_{q=0}^{m-1}\sum_{r=0}^{n-1}x_{rqs}\exp\left({\pm i} {{2\pi jr}\over{n}}\right)\exp\left({\pm i}{{2\pi kq}\over{m}}\right)\exp\left({\pm i}{{2\pi ls}\over{p}}\right)`
For :math:`j=0,1,\ldots,n-1\hbox{ and } k=0,1,\ldots,m-1\hbox{ and } l=0,1,\ldots,p-1`, where :math:`x_{rqs}` is the complex data to
be transformed, :math:`\tilde{x}_{jkl}` is the transformed data, and the sign :math:`\pm` determines the direction of the transform.
|
