NAG Library Function Document
nag_fft_multiple_real (c06fpc)
1
Purpose
nag_fft_multiple_real (c06fpc) computes the discrete Fourier transforms of sequences, each containing real data values.
2
Specification
#include <nag.h> |
#include <nagc06.h> |
void |
nag_fft_multiple_real (Integer m,
Integer n,
double x[],
const double trig[],
NagError *fail) |
|
3
Description
Given
sequences of
real data values
, for
and
, 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
the
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.
4
References
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
5
Arguments
- 1:
– IntegerInput
-
On entry: the number of sequences to be transformed, .
Constraint:
.
- 2:
– IntegerInput
-
On entry: the number of real values in each sequence, .
Constraint:
.
- 3:
– doubleInput/Output
-
On entry: the
data sequences must be stored in
x consecutively. If the data values of the
th sequence to be transformed are denoted by
, for
, 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 .
- 4:
– const doubleInput
-
On entry: 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
- 5:
– NagError *Input/Output
-
The NAG error argument (see
Section 3.7 in How to Use the NAG Library and its Documentation).
6
Error Indicators and Warnings
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
- NE_C06_NOT_TRIG
-
Value of
n and
trig array are incompatible or
trig array not initialized.
- NE_INT_ARG_LT
-
On entry, .
Constraint: .
On entry, .
Constraint: .
7
Accuracy
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
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.
10
Example
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.
10.1
Program Text
Program Text (c06fpce.c)
10.2
Program Data
Program Data (c06fpce.d)
10.3
Program Results
Program Results (c06fpce.r)