NAG Library Function Document

nag_fft_multiple_real (c06fpc)

+− 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_real (c06fpc) computes the discrete Fourier transforms of

m

sequences, each containing

n

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

m

sequences of

n

real data values

x_{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} x_{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 transformed values

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

are complex, but for each value of

p

the

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

form a Hermitian sequence (i.e.,

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

is the complex conjugate of

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

), so they are completely determined by

m n

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

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

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

{\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 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: m – IntegerInput

On entry: the number of sequences to be transformed,

m

Constraint:

m \geq 1

2: n – IntegerInput

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

n

Constraint:

n \geq 1

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

On entry: the

m

data sequences must be stored in x consecutively. If the data values 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} .

On exit: the

m

discrete Fourier transforms in Hermitian form, stored consecutively, overwriting the corresponding original sequences. If the

n

components of the discrete Fourier transform

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

are written as

a_{k}^{p} + {i b}_{k}^{p}

, then for

0 \leq k \leq n / 2

a_{k}^{p}

is in array element

x [(p - 1) \times n + k]

and for

1 \leq k \leq (n - 1) / 2

b_{k}^{p}

is in array element

x [(p - 1) \times n + n - k]

4: trig[ $2 \times n$ ] – 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: 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 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.

NAG Library Function Documentnag_fft_multiple_real (c06fpc)