NAG Library Function Document

nag_fft_multiple_complex (c06frc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

+− 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

1 Purpose

nag_fft_multiple_complex (c06frc) computes the discrete Fourier transforms of

m

sequences, each containing

n

complex data values.

2 Specification

#include <nag.h>

#include <nagc06.h>

void	nag_fft_multiple_complex (Integer m, Integer n, double x[], double y[], const double trig[], NagError *fail)

3 Description

Given

m

sequences of

n

complex data values

z_{j}^{p}

, for

j = 0, 1, \dots, n - 1

and

p = 1, 2, \dots, m

, this function simultaneously calculates the Fourier transforms of all the sequences defined by

{\hat{z}}_{k}^{p} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} z_{j}^{p} \exp (- 2 π i j k / n),   for ​ k = 0, 1, \dots, n - 1; p = 1, 2, \dots, m .

(Note the scale factor

1 / \sqrt{n}

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

{\hat{z}}_{k}^{p} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} z_{j}^{p} \exp (+ 2 π i j k / n) .

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

z_{j}^{p}

and the

{\hat{z}}_{k}^{p}

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.

4 References

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

5 Arguments

1: m – IntegerInput

On entry: the number of sequences to be transformed,

m

Constraint:

m \geq 1

2: n – IntegerInput

On entry: the number of complex values in each sequence,

n

Constraint:

n \geq 1

3: x[ $m \times n$ ] – doubleInput/Output

4: y[ $m \times n$ ] – doubleInput/Output

On entry: the real and imaginary parts of the complex data must be stored in x and y respectively. Each of the

m

sequences must be stored consecutively; hence if the real parts of the

p

th sequence to be transformed are denoted by

x_{j}^{p}

, for

j = 0, 1, \dots, n - 1

, then the

m n

elements of the array x must contain the values

x_{0}^{1}, x_{1}^{1}, \dots, x_{n - 1}^{1}, x_{0}^{2}, x_{1}^{2}, \dots, x_{n - 1}^{2}, \dots, x_{0}^{m}, x_{1}^{m}, \dots, x_{n - 1}^{m} .

The imaginary parts must be ordered similarly in y.

On exit: x and y are overwritten by the real and imaginary parts of the complex transforms.

5: trig[ $2 \times n$ ] – const doubleInput

On entry: 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.

6: fail – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

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, $m = ⟨value⟩$ .
Constraint: $m \geq 1$ .
On entry, $n = ⟨value⟩$ .
Constraint: $n \geq 1$ .

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

Not applicable.

9 Further Comments

The time taken is approximately proportional to

n m \log (n)

, but also depends on the factors of

n

. The function is fastest if the only prime factors of

n

are 2, 3 and 5, and is particularly slow if

n

is a large prime, or has large prime factors.

10 Example

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.

NAG Library Function Documentnag_fft_multiple_complex (c06frc)