There are two main types of DFTs:
ZFFT
or CFFT, for double and single precision,
respectively;
DZFFT or
SCFFT, for double and single precision, respectively; the names for the
latter begin with ZDFFT or CSFFT.
The simplest transforms to describe are those performed on sequences of complex data. Such data are stored as arrays of type complex. The result of a complex FFT is also a complex sequence of the same length and, for the simple interfaces, is written back to the original array. Where multiple (m, say), same-length sequences (of length n) of complex data are to be transformed, the sequences are held in a single complex array; in the simple interfaces the array will be of length m*n containing m end-to-end sequences and the results of the m FFTs are returned in the original array. Expert interfaces are provided which give: greater flexibility in the storage of the original data and results, user provided scaling, and whether results should be written to a separate array or not.
For the simple interfaces, a two dimensional array of complex data, with m rows and n columns is stored in the same order as a set of n sequences of length m (as described above). That is, column elements are stored contiguously and the first element of the next column follows the last element of the current column. In the expert interfaces, column elements may be separated by a fixed step length (increment) while row elements may be separated by a second increment; if the first increment is 1 and the second increment is m then we have the same storage as in the simple interface.
The DFT of a sequence of real data results in a special form of complex sequence known as a Hermitian sequence. The symmetries defining such a sequence mean that it can be fully represented by a set of n real values, where n is the length of the original real sequence. It is therefore conventional for the array containing the real sequence to be overwritten by such a representation of the transformed Hermitian sequence.
In full complex representation, the Hermitian sequence would be a sequence
of n complex values Z(i) for i=0,1,...,n-1, where
Z(n-j) is the complex conjugate of Z(j) for
j=1,2,...,(n-1)/2; Z(0) is real valued; and, if
n is even, Z(n/2) is real valued. In ACML, the representation of
Hermitian sequences used on output from DZFFT routines and on
input to ZDFFT routines is as follows:
let X be an array of length N and with first index 0,
The efficiency of the FFT is maximized by choosing the sequence length to be a power of 2. Good efficiency can also be achieved when the sequence length has small prime factors, up to a factor 13; however, the time taken for an FFT increases as the size of the prime factor increases.