c06 Chapter Contents
c06 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_fft_2d_complex (c06fuc)

## 1  Purpose

nag_fft_2d_complex (c06fuc) computes the two-dimensional discrete Fourier transform of a bivariate sequence of complex data values.

## 2  Specification

 #include #include
 void nag_fft_2d_complex (Integer m, Integer n, double x[], double y[], const double trigm[], const double trign[], NagError *fail)

## 3  Description

nag_fft_2d_complex (c06fuc) computes the two-dimensional discrete Fourier transform of a bivariate sequence of complex data values ${z}_{{j}_{1}{j}_{2}}$, where ${j}_{1}=0,1,\dots ,m-1$, ${j}_{2}=0,1,\dots ,n-1$.
The discrete Fourier transform is here defined by
 $z ^ k 1 k 2 = 1 mn ∑ j 1 = 0 m-1 ∑ j 2 = 0 n-1 z j 1 j 2 exp -2 π i j 1 k 1 m + j 2 k 2 n$
for ${k}_{1}=0,1,\dots ,m-1$; ${k}_{2}=0,1,\dots ,n-1$.
(Note the scale factor of $1/\sqrt{mn}$ in this definition.)
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 $\mathrm{exp}\left(+2\pi i\left(\dots \right)\right)$ in the above formula instead of $\mathrm{exp}\left(-2\pi i\left(\dots \right)\right)$, 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:     mIntegerInput
On entry: the number of rows, $m$, of the bivariate data sequence.
Constraint: ${\mathbf{m}}\ge 1$.
2:     nIntegerInput
On entry: the number of columns, $n$, of the bivariate data sequence.
Constraint: ${\mathbf{n}}\ge 1$.
3:     x[${\mathbf{m}}×{\mathbf{n}}$]doubleInput/Output
4:     y[${\mathbf{m}}×{\mathbf{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 $mn$ elements of x must contain the values
 $x 0,0 , x 0,1 , … , x 0 , n - 1 , x 1,0 , x 1,1 , … , x 1 , n - 1 , … , x m - 1 , 0 , x m - 1 , 1 , … , 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×{\mathbf{m}}$]const doubleInput
6:     trign[$2×{\mathbf{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:     failNagError *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, ${\mathbf{m}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{m}}\ge 1$.
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 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).

The time taken is approximately proportional to $mn\mathrm{log}\left(mn\right)$, 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$ or $n$ is a large prime, or has large prime factors.

## 9  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.

### 9.1  Program Text

Program Text (c06fuce.c)

### 9.2  Program Data

Program Data (c06fuce.d)

### 9.3  Program Results

Program Results (c06fuce.r)