NAG Library Function Document
nag_fft_multiple_complex (c06frc) computes the discrete Fourier transforms of sequences, each containing complex data values.
||nag_fft_multiple_complex (Integer m,
const double trig,
complex data values
, this function simultaneously calculates the Fourier transforms of all the sequences defined by
(Note the scale factor
in this definition.)
The first call of nag_fft_multiple_complex (c06frc) must be preceded by a call to nag_fft_init_trig (c06gzc)
to initialize the array trig
with trigonometric coefficients.
The discrete Fourier transform is sometimes defined using a positive sign in the exponential term
To compute this form, this function should be preceded and followed by a call of nag_conjugate_complex (c06gcc)
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 code is provided for the factors 2, 3, 4, 5 and 6.
Brigham E O (1974) The Fast Fourier Transform Prentice–Hall
Temperton C (1983) Self-sorting mixed-radix fast Fourier transforms J. Comput. Phys. 52 1–23
On entry: the number of sequences to be transformed, .
On entry: the number of complex values in each sequence, .
: the real and imaginary parts of the complex data must be stored in x
respectively. Each of the
sequences must be stored consecutively; hence if the real parts of the
th sequence to be transformed are denoted by
, then the
elements of the array x
must contain the values
The imaginary parts must be ordered similarly in y
are overwritten by the real and imaginary parts of the complex transforms.
– const doubleInput
: trigonometric coefficients as returned by a call of nag_fft_init_trig (c06gzc)
. nag_fft_multiple_complex (c06frc) 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.6
in the Essential Introduction).
6 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).
8 Parallelism and Performance
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 complex data values and prints their discrete Fourier transforms (as computed by nag_fft_multiple_complex (c06frc)). Inverse transforms are then calculated using nag_conjugate_complex (c06gcc)
and nag_fft_multiple_complex (c06frc) and printed out, showing that the original sequences are restored.
10.1 Program Text
Program Text (c06frce.c)
10.2 Program Data
Program Data (c06frce.d)
10.3 Program Results
Program Results (c06frce.r)