# Storage schemes

Each value of the domain, that is, `DFTI_COMPLEX`, `DFTI_REAL`, and `DFTI_CONJUGATE_EVEN` (for the forward as well as the backward transform), determines a subset of the four values for storage schemes: `DFTI_COMPLEX_COMPLEX`, `DFTI_COMPLEX_REAL`, `DFTI_REAL_COMPLEX`, and `DFTI_REAL_REAL`. In Table “Settings for Discrete Configuration Parameters”, these subsets correspond to `DFTI_COMPLEX_STORAGE`, `DFTI_REAL_STORAGE`, and `DFTI_CONJUGATE_EVEN_STORAGE` in the first-column, respectively. Specific examples are presented below to illustrate the storage schemes that are admissible for each domain. See document [3] for the rationale behind this definition of the storage schemes.

### Note

The data is stored in the Fortran style only, that is, the real and imaginary parts are stored side by side.

Storage scheme for complex domain. This setting is recorded in the configuration parameter `DFTI_COMPLEX_STORAGE`. The only value that can be set is `DFTI_COMPLEX_COMPLEX`. Consider a one-dimensional n-length transform of the form

Assume the stride has default value (unit stride) and `DFTI_PLACEMENT` has the default in-place setting.

DFTI_COMPLEX_COMPLEX storage scheme (by default). A typical usage will be as follows.

COMPLEX :: X(0:n-1)

...some other code...

Status = DftiComputeForward( Desc_Handle, X )

``

On input,

`X(j) = wj, j = 0,1,...,n-1.`

On output,

`X(k) = zk , k = 0,1,...,n-1.`

Storage scheme for the real and conjugate even domains. This setting for the storage schemes for these domains is recorded in the configuration parameters `DFTI_REAL_STORAGE` and `DFTI_CONJUGATE_EVEN_STORAGE`. Since a forward real domain corresponds to a conjugate even backward domain, they are considered together. The example uses one-, two- and three-dimensional real to conjugate even transforms. In-place computation is assumed whenever possible (that is, when the input data type matches the output data type).

One-Dimensional Transform

Consider a one-dimensional n-length transform of the form

There is a symmetry:

For even `n: z(n/2+i) = conjg(z(n/2-i))`, `1≤i≤n/2-1`, and moreover `z(0)` and `z(n/2)` are real values.

For odd `n: z(m+i) = conjg(z(m-i+1))`, `1≤i≤m`, and moreover `z(0)` is real value.

`m = floor(n/2)`.

Comparison of the Storage Effects of Complex-to-Complex and Real-to-Complex FFTs for Forward Transform
N=8
Input Vectors | Output Vectors
Complex FFT | Real FFT | complex FFT | real FFT
Complex Data | Real Data | Complex Data | Real Data
Real | Imaginary |  | Real | Imaginary | CCS | Pack | Perm
w0 | 0.000000 | w0 | z0 | 0.000000 | z0 | z0 | z0
w1 | 0.000000 | w1 | Re(z1) | Im(z1) | 0.000000 | Re(z1) | z4
w2 | 0.000000 | w2 | Re(z2) | Im(z2) | Re(z1) | Im(z1) | Re(z1)
w3 | 0.000000 | w3 | Re(z3) | Im(z3) | Im(z1) | Re(z2) | Im(z1)
w4 | 0.000000 | w4 | z4 | 0.000000 | Re(z2) | Im(z2) | Re(z2)
w5 | 0.000000 | w5 | Re(z3) | -Im(z3) | Im(z2) | Re(z3) | Im(z2)
w6 | 0.000000 | w6 | Re(z2) | -Im(z2) | Re(z3) | Im(z3) | Re(z3)
w7 | 0.000000 | w7 | Re(z1) | -Im(z1) | Im(z3) | z4 | Im(z3)
|  |  |  |  | z4 |  |
|  |  |  |  | 0.000000 |  |

N=7
Input Vectors | Output Vectors
Complex FFT | Real FFT | complex FFT | real FFT
Complex Data | Real Data | Complex Data | Real Data
Real | Imaginary |  | Real | Imaginary | CCS | Pack | Perm
w0 | 0.000000 | w0 | z0 | 0.000000 | z0 | z0 | z0
w1 | 0.000000 | w1 | Re(z1) | Im(z1) | 0.000000 | Re(z1) | Re(z1)
w2 | 0.000000 | w2 | Re(z2) | Im(z2) | Re(z1) | Im(z1) | Im(z1)
w3 | 0.000000 | w3 | Re(z3) | Im(z3) | Im(z1) | Re(z2) | Re(z2)
w4 | 0.000000 | w4 | Re(z3) | -Im(z3) | Re(z2) | Im(z2) | Im(z2)
w5 | 0.000000 | w5 | Re(z2) | -Im(z2) | Im(z2) | Re(z3) | Re(z3)
w6 | 0.000000 | w6 | Re(z1) | -Im(z1) | Re(z3) | Im(z3) | Im(z3)
|  |  |  |  | Im(z3) |  |

Comparison of the Storage Effects of Complex-to-Complex and Complex-to-Real FFTs for Backward Transform
N=8
Input Vectors | Output Vectors
Complex FFT | Real FFT | complex FFT | real FFT
Complex Data | Real Data | Complex Data | Real Data
Real | Imaginary |  | Real | Imaginary | CCS | Pack | Perm
w0 | 0.000000 | w0 | z0 | 0.000000 | z0 | z0 | z0
w1 | 0.000000 | w1 | Re(z1) | Im(z1) | 0.000000 | Re(z1) | z4
w2 | 0.000000 | w2 | Re(z2) | Im(z2) | Re(z1) | Im(z1) | Re(z1)
w3 | 0.000000 | w3 | Re(z3) | Im(z3) | Im(z1) | Re(z2) | Im(z1)
w4 | 0.000000 | w4 | z4 |  | Re(z2) | Im(z2) | Re(z2)
w5 | 0.000000 | w5 | Re(z3) | -Im(z3) | Im(z2) | Re(z3) | Im(z2)
w6 | 0.000000 | w6 | Re(z2) | -Im(z2) | Re(z3) | Im(z3) | Re(z3)
w7 | 0.00000 | w7 | Re(z1) | -Im(z1) | Im(z3) | z4 | Im(z3)
|  |  |  |  | z4 |  |
|  |  |  |  | 0.000000 |  |

N=7
Input Vectors | Output Vectors
Complex FFT | Real FFT | complex FFT | real FFT
Complex Data | Real Data | Complex Data | Real Data
Real | Imaginary |  | Real | Imaginary | CCS | Pack | Perm
w0 | 0.000000 | w0 | z0 | 0.000000 | z0 | z0 | z0
w1 | 0.000000 | w1 | Re(z1) | Im(z1) | 0.000000 | Re(z1) | Re(z1)
w2 | 0.000000 | w2 | Re(z2) | Im(z2) | Re(z1) | Im(z1) | Im(z1)
w3 | 0.000000 | w3 | Re(z3) | Im(z3) | Im(z1) | Re(z2) | Re(z2)
w4 | 0.000000 | w4 | Re(z3) | -Im(z3) | Re(z2) | Im(z2) | Im(z2)
w5 | 0.000000 | w5 | Re(z2) | -Im(z2) | Im(z2) | Re(z3) | Re(z3)
w6 | 0.000000 | w6 | Re(z1) | -Im(z1) | Re(z3) | Im(z3) | Im(z3)
|  |  |  |  | Im(z3) |  |

Assume that the stride has the default value (unit stride).

This complex conjugate-symmetric vector can be stored in the complex array of size m+1 or in the real array of size 2m+2 or 2m depending on packed format.

Two-Dimensional Transform

Each of the real-to-complex functions computes the forward FFT of a two-dimensional real matrix according to the mathematical equation

`tk,l = cmplx(rk,l,0)`, where `rk,l` is a real input matrix, `0≤k≤m-1`, `0 ≤l≤n-1`. The mathematical result `zi,j, 0≤i≤m-1, 0≤j≤n-1`, is the complex matrix of size `(m,n)`. Each column is the complex conjugate-symmetric vector as follows:

For even `m`:

for `0 ≤j≤n-1`,

`z(m/2+i,j) = conjg(z(m/2-i,j))`,`1≤i≤m/2-1`.

Moreover, `z(0,j)` and `z(m/2,j)` are real values for `j=0` and `j=n/2`.

For odd `m:`

for `0≤j≤n-1`,

`z(s+i,j) = conjg(z(s-i,j))`, `1≤i≤s-1`,

where `s = floor(m/2)`.

Moreover, `z(0,j)` are real values for `j=0` and `j=n/2`.

This mathematical result can be stored in the real two-dimensional array of size:

`(m+2,n+2)` (CCS format), or

`(m,n)` (Pack or Perm formats), or

`(2*(m/1+1), n)` (CCE format, Fortran-interface),

`((m, 2*(n/2+1))` (CCE format, C-interface)

or in the complex two-dimensional array of size:

`(m/2+1, n)` (CCE format, Fortran-interface),

`(m, n/2+1)` (CCE format, C-interface)

Since the multidimensional array data are arranged differently in Fortran and C (see Strides), the output array that holds the computational result contains complex conjugate-symmetric columns (for Fortran) or complex conjugate-symmetric rows (for C).

The following tables give examples of output data layout in Pack format for a forward two-dimensional real-to-complex FFT of a 6-by-4 real matrix. Note that the same layout is used for the input data of the corresponding backward complex-to-real FFT.

Fortran-interface Data Layout for a 6-by-4 Matrix
z(1,1) | Re z(1,2) | Im z(1,2) | z(1,3)
Re z(2,1) | Re z(2,2) | Re z(2,3) | Re z(2,4)
Im z(2,1) | Im z(2,2) | Im z(2,3) | Im z(2,4)
Re z(3,1) | Re z(3,2) | Re z(3,3) | Re z(3,4)
Im z(3,1) | Im z(3,2) | Im z(3,3) | Im z(3,4)
z(4,1) | Re z(4,2) | Im z(4,2) | z(4,3)

For the above example, the stride array is taken to be (0, 1, 6).

C-interface Data Layout for a 6-by-4 Matrix
z(1,1) | Re z(1,2) | Im z(1,2) | z(1,3)
Re z(2,1) | Re z(2,2) | Im z(2,2) | Re z(2,3)
Im z(2,1) | Re z(3,2) | Im z(3,2) | Im z(2,3)
Re z(3,1) | Re z(4,2) | Im z(4,2) | Re z(3,3)
Im z(3,1) | Re z(5,2) | Im z(5,2) | Im z(3,3)
z(4,1) | Re z(6,2) | Im z(6,2) | z(4,3)

For the second example, the stride array is taken to be (0, 4, 1).

See also Packed formats.

Three-Dimensional Transform

Each of the real-to-complex functions computes the forward FFT of a three-dimensional real matrix according to the mathematical equation

`tp,l,s = cmplx(rp,l,s,0)`, where `rp,l,s` is a real input matrix, `0 ≤ k ≤ m-1, 0 ≤ l ≤ n-1, 0 ≤ s ≤ k-1`. The mathematical result `zi,j,q, 0 ≤ i ≤ m-1, 0 ≤ j ≤ n-1, 0 ≤ q ≤ k-1` is the complex matrix of size `(m,n,k)`, which is a complex conjugate-symmetric, or conjugate even, matrix as follows:

`zm1,n1,k1 = conjg(zm-m1,n-n1,k-k1)`, where each dimension is periodic.

This mathematical result can be stored in the real three-dimensional array of size:

`(m/2+1,n,k)` (CCE format, Fortran-interface),

`(m,n,k/2+1)` (CCE format, C-interface).

Since the multidimensional array data are arranged differently in Fortran and C (see Strides), the output array that holds the computational result contains complex conjugate-symmetric columns (for Fortran) or complex conjugate-symmetric rows (for C).

### Note

There is one packed format for 3D REAL FFT - CCE format. In both in-place and out-of-place REAL FFT, for real data, the stride and distance parameters are in REAL units and for complex data, they are in COMPLEX units. So, elements of input and output data can be placed in different elements of input-output array of the in-place FFT.

1. DFTI_REAL_REAL for real domain, DFTI_COMPLEX_REAL for conjugate even domain (by default). It is used for 1D and 2D REAL FFT.

   - A typical usage of in-place transform is as follows:

     // m = floor( n/2 )

     REAL :: X(0:2*m+1)

     ...some other code...

     ...assuming inplace transform...

     Status = DftiComputeForward( Desc_Handle, X )

     On input,

     `X(`j`) = `wj`, j = 0,1,...,n-1`.

     On output,

     Output data stored in one of formats: Pack, Perm or CCS (see Packed formats).

     CCS format: `X(2*k) = Re(zk), X(2*k+1) = Im(zk), k = 0,1,...,m`.

     Pack format: ``

     even n: `X(0) = Re(z0), X(2*k-1) = Re(zk), X(2*k) = Im(zk), k = 1,...,m-1, and X(n-1) = Re(zm)`

     odd n: `X(0) = Re(z0), X(2*k-1) = Re(zk), X(2*k) = Im(zk), k = 1,...,m`

     Perm format: ``

     even n: `X(0) = Re(z0), X(1) = Re(zm), X(2*k) = Re(zk), X(2*k+1) = Im(zk), k = 1,...,m-1,`

     odd n: `X(0) = Re(z0), X(2*k-1) = Re(zk), X(2*k) = Im(zk), k = 1,...,m`.

     See Example “One-dimensional In-place FFT (Fortran Interface)”, Example “One-dimensional In-place FFT (C Interface)”, Example “Two-dimensional FFT (Fortran Interface)”, and Example “Two-dimensional FFT (C Interface)”.

     Input and output data exchange the roles in the backward transform.

   - A typical usage of out-of-place transform is as follows:

     // m = floor( n/2 )

     REAL :: X(0:n-1)

     REAL :: Y(0:2*m+1)

     ...some other code...

     ...assuming out-of-place transform...

     Status = DftiComputeForward( Desc_Handle, X, Y )

     On input, `X(j) = wj, j = 0,1,...,n-1.`

     On output,

     Output data stored in one of formats: Pack, Perm or CCS (see Packed formats).

     CCS format: `Y(2*k) = Re(zk), Y(2*k+1) = Im(zk), k = 0,1,...,m`.

     Pack format: ``

     even n: `Y(0) = Re(z0), Y(2*k-1) = Re(zk), Y(2*k) = Im(zk), k = 1,...,m-1, and Y(n-1) = Re(zm)`

     odd n: `Y(0) = Re(z0), Y(2*k-1) = Re(zk), Y(2*k) = Im(zk), k = 1,...,m`

     Perm format:

     even n: `Y(0) = Re(z0), Y(1) = Re(zm), Y(2*k) = Re(zk) , Y(2*k+1) = Im(zk), k = 1,...,m-1`,

     odd n: `Y(0) = Re(z0), Y(2*k-1) = Re(zk), Y(2*k) = Im(zk), k = 1,...,m`.

     Notice that if the stride of the output array is not set to the default value unit stride, the real and imaginary parts of one complex element will be placed with this stride.

     For example:

     CCS format: `Y(2*k*s) = Re(zk), Y((2*k+1)*s) = Im(zk), k = 0,1, ..., m, s - stride`.

     See Example “One-dimensional Out-of-place FFT (Fortran Interface)” and Example “One-dimensional Out-of-place FFT (C Interface)”.

     Input and output data exchange the roles in the backward transform.

2. DFTI_REAL_REAL for real domain, DFTI_COMPLEX_COMPLEX for conjugate even domain. It is used for 1D, 2D and 3D REAL FFT. The CCE format is set by default. You must explicitly set the storage scheme in this case, because its value is not the default one.

   - A typical usage of in-place transform is as follows:

     // m = floor( n/2 )

     REAL :: X(0:m*2)

     ...some other code...

     ...assuming in-place transform...

     Status = DftiSetValue( Desc_Handle, DFTI_CONJUGATE_EVEN_STORAGE, DFTI_COMPLEX_COMPLEX)

     ...

     Status = DftiComputeForward( Desc_Handle, X)

     On input,

     `X(j) = wj, j` = 0,1,...,`n`-1.

     On output,

     `X(2*k) = Re(zk), X(2*k+1) = Im(zk), k` = 0,1,...,`m`.

     See Example “Two-Dimensional REAL In-place FFT (Fortran Interface)”.

     Input and output data exchange the roles in the backward transform.

   - A typical usage of out-of-place transform is as follows:

     // m = floor( n/2 )

     REAL :: X(0:n-1)

     COMPLEX :: Y(0:m)

     ...some other code...

     ...assuming out-of-place transform...

     Status = DftiSetValue( Desc_Handle, DFTI_CONJUGATE_EVEN_STORAGE, DFTI_COMPLEX_COMPLEX)

     ...

     Status = DftiComputeForward( Desc_Handle, X, Y )

     On input,

     `X(j) = wj, j = 0,1,...,n-1`.

     On output,

     `Y(k) = zk, k = 0,1,...,m.`

     See Example “Two-Dimensional REAL Out-of-place FFT (Fortran Interface)” and Example “Three-Dimensional REAL FFT (C Interface)”

     Input and output data exchange the roles in the backward transform.

3. DFTI_REAL_COMPLEX for real domain, DFTI_COMPLEX_COMPLEX for conjugate even domain. It is not used in the current version. See the Note for details. A typical usage is as follows:

   // m = floor( n/2 )

   COMPLEX :: X(0:m)

   ...some other code...

   ...inplace transform...

   Status = DftiComputeForward( Desc_Handle, X )

   On input, ``

   `X(j) = wj, j = 0,1,...,n-1.`

   That is, the imaginary parts of `X(j)` are zero.

   On output,

   `Y(k) = zk, k = 0,1,...,m,`

   where `m` is `floor( n/2 )`.

Parent topic: Configuration Settings