NAG Library Function Document

nag_fft_2d_complex (c06fuc)

The first call of nag_fft_2d_complex (c06fuc) must be preceded by calls to nag_fft_init_trig (c06gzc) to initialize the trigm and trign arrays with trigonometric coefficients according to the value of m and n respectively.

To compute the inverse discrete Fourier transform, defined with

\exp (+ 2 π i (\dots))

in the above formula instead of

\exp (- 2 π i (\dots))

, this function should be preceded and followed by calls of nag_conjugate_complex (c06gcc) to form the complex conjugates of the data values and the transform.

This function calls nag_fft_multiple_complex (c06frc) to perform multiple one-dimensional discrete Fourier transforms by the fast Fourier transform algorithm in Brigham (1974).

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 rows,

m

, of the bivariate data sequence.

Constraint:

m \geq 1

2: n – IntegerInput

On entry: the number of columns,

n

, of the bivariate data sequence.

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 values must be stored in arrays x and y respectively. Each row of the data must be stored consecutively; hence if the real parts of

z_{j_{1}, j_{2}}

are denoted by

x_{j_{1}, j_{2}}

, for

j_{1} = 0, 1, \dots, m - 1

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

, then the

m n

elements of x must contain the values

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

The imaginary parts must be ordered similarly in y.

On exit: the real and imaginary parts respectively of the corresponding elements of the computed transform.

5: trigm[ $2 \times m$ ] – const doubleInput

6: trign[ $2 \times n$ ] – const doubleInput

On entry: trigm and trign must contain trigonometric coefficients as returned by calls of nag_fft_init_trig (c06gzc). nag_fft_2d_complex (c06fuc) performs a simple check to ensure that both arrays have been initialized and that they are compatible with m and n. If

m = n

the same array may be supplied for trigm and trign.

7: 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 m and trigm array are incompatible or trigm array not initialized.
Value of n and trign array are incompatible or trign 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

m n \log (m n)

, but also depends on the factorization of the individual dimensions

m

and

n

. The function is somewhat faster than average if their only prime factors are 2, 3 or 5; and fastest of all if they are powers of 2; it is particularly slow if

m

n

is a large prime, or has large prime factors.

10 Example

This program 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_2d_complex (c06fuc)

+− Contents

1 Purpose

2 Specification

3 Description