DFTI_COMPLEX_STORAGE, DFTI_REAL_STORAGE, DFTI_CONJUGATE_EVEN_STORAGE

Depending on the value of configuration parameter DFTI_FORWARD_DOMAIN, the implementation of FFT supports several storage schemes for input and output data (see document [3] for the rationale behind the definition of the storage schemes). The data elements are placed within contiguous memory blocks, defined with generalized strides (see DFTI_INPUT_STRIDES, DFTI_OUTPUT_STRIDES). For multiple transforms, each nth set of data (where nth≥0) should be located within the same memory block, and the data sets should be placed at a distance from each other (see DFTI_NUMBER_OF TRANSFORMS and DFTI_INPUT DISTANCE, DFTI_OUTPUT_DISTANCE).

Note

In C/C++, avoid setting up multidimensional arrays with lists of pointers to one-dimensional arrays. Instead use a one-dimensional array with the explicit indexing to access the data elements.

C notation is used in this section to describe association of mathematical entities with the data elements stored in memory. FFT Examples demonstrate the usage of storage formats in both C and Fortran.

Storage schemes for complex domain. For the DFTI_COMPLEX forward domain, both input and output sequences belong to the complex domain. In this case, the configuration parameter DFTI_COMPLEX_STORAGE can have one of the two values: DFTI_COMPLEX_COMPLEX (default) or DFTI_REAL_REAL.

Note

In the Intel MKL FFT implementation, storage schemes for a forward complex domain and the respective backward complex domain are the same.

With DFTI_COMPLEX_COMPLEX storage, the complex-valued data sequence is referenced by a single complex parameter Z so that complex-valued element z_{k1, k2, ..., kd} of the sequence is located at Z[nth*distance + stride₀ + k₁*stride₁ + k₂*stride₂+ ... k_d*stride_d] as a structure consisting of the real and imaginary parts.

The following example illustrates a typical usage of the DFTI_COMPLEX_COMPLEX storage:

complex :: x(n)

...

! on input, for i=1,...,N: x(i) = ri-1

status = DftiComputeForward( desc_handle, x )

! on output, for i=1,...,N: x(i) = zi-1

With the DFTI_REAL_REAL storage, the complex-valued data sequence is referenced by two real parameters ZRe and ZIm so that complex-valued element z_{k1, k2, ..., kd} of the sequence is computed as ZRe[nth*distance + stride₀ + k₁*stride₁ + k₂*stride₂+ ... k_d*stride_d] + √(-1) × ZIm[nth*distance + stride₀ + k₁*stride₁ + k₂*stride₂+ ... k_d*stride_d].

A typical usage of the DFTI_REAL_REAL storage is illustrated by the following example:

real :: xre(n), xim(n)

...

status = DftiSetValue( desc_handle, DFTI_COMPLEX_STORAGE, DFTI_REAL_REAL)

! on input, for i=1,...,N: cmplx(xre(i),xim(i)) = ri-1

status = DftiComputeForward( desc_handle, xre, xim )

! on output, for i=1,...,N: cmplx(xre(i),xim(i)) = zi-1

Storage scheme for the real and conjugate-even domains. The setting for the storage schemes for real and conjugate-even 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 below 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)), m = floor(n/2), 1≤i≤m, and moreover z(0) is real value.

Assume that the stride has the default value of one.

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 which packed format is used.

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

The mathematical result z_j,p, 0≤j≤m-1, 0≤p≤n-1, is the complex matrix of size (m,n).

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

or in the complex two-dimensional array of size:

Since the multidimensional array data are arranged differently in Fortran and C (see DFTI_INPUT_STRIDES, DFTI_OUTPUT_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.

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

For the second example, the stride array is (0, 4, 1). See DFTI_INPUT_STRIDES, DFTI_OUTPUT_STRIDES for details.

See also DFTI_PACKED_FORMAT.

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

The mathematical result z_j,t,q, 0 ≤ j ≤ m-1, 0 ≤ t ≤ 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:

z_m1,n1,k1 = conjg(z_{m-m1,n-n1,k-k1}), where each dimension is periodic.

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

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

Note

CCE is the only packed format for a three-dimensional real FFT. 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 the 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(p) = r_p, p = 0,1,...,n-1.

     On output,

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

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

     Pack format:

     even n: X(0) = Re(z₀), X(2*k-1) = Re(z_k), X(2*k) = Im(z_k), k = 1,...,m-1, and X(n-1) = Re(z_m)

     odd n: X(0) = Re(z₀), X(2*k-1) = Re(z_k), X(2*k) = Im(z_k), k = 1,...,m

     Perm format:

     even n: X(0) = Re(z₀), X(1) = Re(z_m), X(2*k) = Re(z_k), X(2*k+1) = Im(z_k), k = 1,...,m-1,

     odd n: X(0) = Re(z₀), X(2*k-1) = Re(z_k), X(2*k) = Im(z_k), 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 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(p) = r_p, p = 0,1,...,n-1.

     On output,

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

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

     Pack format:

     even n: Y(0) = Re(z₀), Y(2*k-1) = Re(z_k), Y(2*k) = Im(z_k), k = 1,...,m-1, and Y(n-1) = Re(z_m)

     odd n: Y(0) = Re(z₀), Y(2*k-1) = Re(z_k), Y(2*k) = Im(z_k), k = 1,...,m

     Perm format:

     even n: Y(0) = Re(z₀), Y(1) = Re(z_m), Y(2*k) = Re(z_k) , Y(2*k+1) = Im(z_k), k = 1,...,m-1,

     odd n: Y(0) = Re(z₀), Y(2*k-1) = Re(z_k), Y(2*k) = Im(z_k), 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(z_k), Y((2*k+1)*s) = Im(z_k), 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 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(p) = r_p, p = 0,1,...,n-1.

     On output,

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

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

     Input and output data exchange 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(p) = r_p, p = 0,1,...,n-1.

     On output,

     Y(k) = z_k, 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 roles in the backward transform.