NAG Library Function Document

nag_fft_multiple_hermitian (c06fqc)

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

m

Hermitian sequences, each containing

n

complex data values.

2 Specification

#include <nag.h>

#include <nagc06.h>

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

3 Description

Given

m

Hermitian 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{x}}_{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 transformed values are purely real.

The first call of nag_fft_multiple_hermitian (c06fqc) 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{x}}_{k}^{p} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} z_{j}^{p} \exp (+ 2 π i j k / n) .

For that form, this function should be preceded by a call to nag_multiple_conjugate_hermitian (c06gqc) to form the complex conjugates of the

{\hat{z}}_{j}^{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 included 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 data values in each sequence,

n

Constraint:

n \geq 1

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

On entry: the

m

Hermitian sequences must be stored consecutively in x in Hermitian form. Sequence 1 should occupy the first

n

elements of x, sequence 2 the elements

n

2 n - 1

, so that in general sequence

p

occupies the array elements

(p - 1) n

p n - 1

. If the

n

data values

z_{j}^{p}

are written as

x_{j}^{p} + {i y}_{j}^{p}

, then for

0 \leq j \leq n / 2

x_{j}^{p}

should be in array element

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

and for

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

y_{j}^{p}

should be in array element

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

On exit: the components of the

m

discrete Fourier transforms, stored consecutively. Transform

p

occupies the elements

(p - 1) n

p n - 1

of x overwriting the corresponding original sequence; thus if the

n

components of the discrete Fourier transform are denoted by

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

, for

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

, then the

m n

elements of the array x contain the values

{\hat{x}}_{0}^{1}, {\hat{x}}_{1}^{1}, \dots, {\hat{x}}_{n - 1}^{1}, {\hat{x}}_{0}^{2}, {\hat{x}}_{1}^{2}, \dots, {\hat{x}}_{n - 1}^{2}, \dots, {\hat{x}}_{0}^{m}, {\hat{x}}_{1}^{m}, \dots, {\hat{x}}_{n - 1}^{m} .

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_hermitian (c06fqc) 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 which are assumed to be Hermitian sequences of complex data stored in Hermitian form. The sequences are expanded into full complex form using nag_multiple_hermitian_to_complex (c06gsc) and printed. The discrete Fourier transforms are then computed (using nag_fft_multiple_hermitian (c06fqc)) and printed out. Inverse transforms are then calculated by calling nag_fft_multiple_real (c06fpc) followed by nag_multiple_conjugate_hermitian (c06gqc) showing that the original sequences are restored.

NAG Library Function Documentnag_fft_multiple_hermitian (c06fqc)