c06fp: FL CL CPP AD

NAG CL Interface
c06fpc (withdraw_fft_real_1d_multi_rfmt)

Note: this function is deprecated and will be withdrawn at Mark 30.2. Replaced by c06pqc.

Old Code

nag_sum_withdraw_fft_real_1d_multi_rfmt(m, n, x, trig, &fail);

New Code

nag_sum_fft_realherm_1d_multi_col(Nag_ForwardTransform, n, m, x, &fail);

The mapping of input elements is as follows:

for j=0,1,…,m-1
- $J = j \times (n + 2)$ ;
- $x [J + i] \leftarrow x [j \times n + i]$ , for $i = 0, 1, \dots, n - 1$ ;
- $x [J + n]$ and $x [J + n + 1]$ need not be set.

The mapping of output elements is as follows:

for j=0,1,…,m-1
- $J = j \times (n + 2)$ ;
- $x [J + 2 \times i] \leftarrow x [j \times n + i]$ , for $i = 0, 1, \dots, n / 2$ (real parts);
- $x [J + 2 \times i + 1] \leftarrow x [j \times n + n - i]$ , for $i = 1, 2, \dots, (n - 1) / 2$ (imaginary parts);
- $x [J + 1] = 0$ ;
- $x [J + n + 1] = 0$ when n is even.

Keyword Search:

NAG Library Manual, Mark 28.3

Interfaces: FL CL CPP AD

NAG CL Interface Introduction

C06 (Sum) Chapter Contents

C06 (Sum) Chapter Introduction

c06fp: FL CL CPP AD

▸▿ 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

Settings help

CL Name Style:
Short (a00aac)
Long (impl_details)
Full (nag_info_impl_details)

1 Purpose

c06fpc computes the discrete Fourier transforms of

m

sequences, each containing

n

real data values.

2 Specification

#include <nag.h>

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

The function may be called by the names: c06fpc, nag_sum_withdraw_fft_real_1d_multi_rfmt or nag_fft_multiple_real.

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 c06fpc must be preceded by a call to 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 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$ – Integer Input

On entry: the number of sequences to be transformed,

m

Constraint:

m \geq 1

2: $n$ – Integer Input

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

n

Constraint:

n \geq 1

3: $x [m \times n]$ – double Input/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 double Input

On entry: trigonometric coefficients as returned by a call of c06gzc. 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 7 in the Introduction to the NAG Library CL Interface).

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

c06fpc is not threaded in any implementation.

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 c06fpc). The Fourier transforms are expanded into full complex form using c06gsc and printed. Inverse transforms are then calculated by calling c06gqc followed by c06fqc showing that the original sequences are restored.

c06fp: FL CL CPP AD

NAG CL Interfacec06fpc (withdraw_​fft_​real_​1d_​multi_​rfmt)

Old Code

New Code

▸▿ 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

NAG CL Interface
c06fpc (withdraw_fft_real_1d_multi_rfmt)