NAG Library Function Document

nag_fft_multid_full (c06pjc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

nag_fft_multid_full (c06pjc) computes the multidimensional discrete Fourier transform of a multivariate sequence of complex data values.

2 Specification

#include <nag.h>

#include <nagc06.h>

void	nag_fft_multid_full (Nag_TransformDirection direct, Integer ndim, const Integer nd[], Integer n, Complex x[], NagError *fail)

3 Description

nag_fft_multid_full (c06pjc) computes the multidimensional discrete Fourier transform of a multidimensional sequence of complex data values

z_{j_{1} j_{2} \dots j_{m}}

, where

j_{1} = 0, 1, \dots, n_{1} - 1, j_{2} = 0, 1, \dots, n_{2} - 1

, and so on. Thus the individual dimensions are

n_{1}, n_{2}, \dots, n_{m}

, and the total number of data values is

n = n_{1} \times n_{2} \times \dots \times n_{m}

The discrete Fourier transform is here defined (e.g., for

m = 2

) by:

{\hat{z}}_{k_{1}, k_{2}} = \frac{1}{\sqrt{n}} \sum_{j_{1} = 0}^{n_{1} - 1} \sum_{j_{2} = 0}^{n_{2} - 1} z_{j_{1} j_{2}} \times \exp (\pm 2 π i (\frac{j_{1} k_{1}}{n_{1}} + \frac{j_{2} k_{2}}{n_{2}})),

where

k_{1} = 0, 1, \dots, n_{1} - 1

and

k_{2} = 0, 1, \dots, n_{2} - 1

. The plus or minus sign in the argument of the exponential terms in the above definition determine the direction of the transform: a minus sign defines the forward direction and a plus sign defines the backward direction.

The extension to higher dimensions is obvious. (Note the scale factor of

\frac{1}{\sqrt{n}}

in this definition.)

A call of nag_fft_multid_full (c06pjc) with

direct = Nag_ForwardTransform

followed by a call with

direct = Nag_BackwardTransform

will restore the original data.

The data values must be supplied in a one-dimensional array using column-major storage ordering of multidimensional data (i.e., with the first subscript

j_{1}

varying most rapidly).

This function uses a variant of the fast Fourier transform (FFT) algorithm (see Brigham (1974)) known as the Stockham self-sorting algorithm, which is described in Temperton (1983).

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: direct – Nag_TransformDirectionInput

On entry: if the forward transform as defined in Section 3 is to be computed, then direct must be set equal to Nag_ForwardTransform.

If the backward transform is to be computed then direct must be set equal to Nag_BackwardTransform.

Constraint:

direct = Nag_ForwardTransform

Nag_BackwardTransform

2: ndim – IntegerInput

On entry:

m

, the number of dimensions (or variables) in the multivariate data.

Constraint:

ndim \geq 1

3: nd[ndim] – const IntegerInput

On entry: the elements of nd must contain the dimensions of the ndim variables; that is,

nd [i - 1]

must contain the dimension of the

i

th variable.

Constraints:

$nd [i - 1] \geq 1$ , for $i = 1, 2, \dots, ndim$ ;
$nd [i - 1]$ must have less than $31$ prime factors (counting repetitions), for $i = 1, 2, \dots, ndim$ .

4: n – IntegerInput

On entry:

n

, the total number of data values.

Constraint: n must equal the product of the first ndim elements of the array nd.

5: x[n] – ComplexInput/Output

On entry: the complex data values. Data values are stored in x using column-major ordering for storing multidimensional arrays; that is,

z_{j_{1} j_{2} \dots j_{m}}

is stored in

x [j_{1} + n_{1} j_{2} + n_{1} n_{2} j_{3} + \dots]

On exit: the corresponding elements of the computed transform.

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_BAD_PARAM: On entry, argument $〈value〉$ had an illegal value.
NE_INT: On entry, $ndim = 〈value〉$ .
Constraint: $ndim \geq 1$ .
NE_INT_2: $nd [i - 1]$ must have less than $31$ prime factors: $nd [i - 1] = 〈value〉$ and $i = 〈value〉$ .; n must equal the product of the dimensions held in array nd: $n = 〈value〉$ , product of nd elements is $〈value〉$ .; On entry $nd [i - 1] = 〈value〉$ and $i = 〈value〉$ .
Constraint: $nd [i - 1] \geq 1$ .
NE_INTERNAL_ERROR: An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.

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 Further Comments

The time taken is approximately proportional to

n \times \log n

, but also depends on the factorization of the individual dimensions

nd [i - 1]

. nag_fft_multid_full (c06pjc) is faster if the only prime factors are

2

3

5

; and fastest of all if they are powers of

2

9 Example

This example reads in a bivariate sequence of complex data values and prints the two-dimensional Fourier transform. It then performs an inverse transform and prints the sequence so obtained, which may be compared to the original data values.

NAG Library Function Documentnag_fft_multid_full (c06pjc)