NAG Library Function Document
nag_fft_multiple_real (c06fpc) computes the discrete Fourier transforms of sequences, each containing real data values.
||nag_fft_multiple_real (Integer m,
const double trig,
real data values
, this function simultaneously calculates the Fourier transforms of all the sequences defined by
(Note the scale factor
in this definition.)
The transformed values
are complex, but for each value of
form a Hermitian sequence (i.e.,
is the complex conjugate of
), so they are completely determined by
real numbers. The first call of nag_fft_multiple_real (c06fpc)
must be preceded by a call to nag_fft_init_trig (c06gzc)
to initialize the array trig
with trigonometric coefficients according to the value of n
The discrete Fourier transform is sometimes defined using a positive sign in the exponential term
To compute this form, this function should be followed by a call to nag_multiple_conjugate_hermitian (c06gqc)
to form the complex conjugates of the
The function uses a variant of the fast Fourier transform algorithm (Brigham (1974)
) known as the Stockham self-sorting algorithm, which is described in Temperton (1983)
. Special coding is provided for the factors 2, 3, 4, 5 and 6.
Brigham E O (1974) The Fast Fourier Transform Prentice–Hall
Temperton C (1983) Fast mixed-radix real Fourier transforms J. Comput. Phys. 52 340–350
On entry: the number of sequences to be transformed, .
On entry: the number of real values in each sequence, .
data sequences must be stored in x
consecutively. If the data values of the
th sequence to be transformed are denoted by
, then the
elements of the array x
must contain the values
On exit: the discrete Fourier transforms in Hermitian form, stored consecutively, overwriting the corresponding original sequences. If the components of the discrete Fourier transform are written as , then for , is in array element and for , is in array element .
– const doubleInput
: trigonometric coefficients as returned by a call of nag_fft_init_trig (c06gzc)
. nag_fft_multiple_real (c06fpc)
makes a simple check to ensure that trig
has been initialized and that the initialization is compatible with the value of n
– NagError *Input/Output
The NAG error argument (see Section 3.7
in How to Use the NAG Library and its Documentation).
Error Indicators and Warnings
Dynamic memory allocation failed.
Value of n
array are incompatible or trig
array not initialized.
On entry, .
On entry, .
Some indication of accuracy can be obtained by performing a subsequent inverse transform and comparing the results with the original sequence (in exact arithmetic they would be identical).
Parallelism and Performance
nag_fft_multiple_real (c06fpc) is not threaded in any implementation.
The time taken is approximately proportional to , but also depends on the factors of . The function is fastest if the only prime factors of are 2, 3 and 5, and is particularly slow if is a large prime, or has large prime factors.
This program reads in sequences of real data values and prints their discrete Fourier transforms (as computed by nag_fft_multiple_real (c06fpc)
). The Fourier transforms are expanded into full complex form using nag_multiple_hermitian_to_complex (c06gsc)
and printed. Inverse transforms are then calculated by calling nag_multiple_conjugate_hermitian (c06gqc)
followed by nag_fft_multiple_hermitian (c06fqc)
showing that the original sequences are restored.
Program Text (c06fpce.c)
Program Data (c06fpce.d)
Program Results (c06fpce.r)