c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

NAG Library Function Documentnag_sum_fft_real_2d (c06pvc)

1  Purpose

nag_sum_fft_real_2d (c06pvc) computes the two-dimensional discrete Fourier transform of a bivariate sequence of real data values.

2  Specification

 #include #include
 void nag_sum_fft_real_2d (Integer m, Integer n, const double x[], Complex y[], NagError *fail)

3  Description

nag_sum_fft_real_2d (c06pvc) computes the two-dimensional discrete Fourier transform of a bivariate sequence of real data values ${x}_{{j}_{1}{j}_{2}}$, for ${j}_{1}=0,1,\dots ,m-1$ and ${j}_{2}=0,1,\dots ,n-1$.
The discrete Fourier transform is here defined by
 $z^ k1 k2 = 1mn ∑ j1=0 m-1 ∑ j2=0 n-1 x j1 j2 × exp -2πi j1 k1 m + j2 k2 n ,$
where ${k}_{1}=0,1,\dots ,m-1$ and ${k}_{2}=0,1,\dots ,n-1$. (Note the scale factor of $\frac{1}{\sqrt{mn}}$ in this definition.)
The transformed values ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}}$ are complex. Because of conjugate symmetry (i.e., ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}}$ is the complex conjugate of ${\stackrel{^}{z}}_{\left(m-{k}_{1}\right){k}_{2}}$), only slightly more than half of the Fourier coefficients need to be stored in the output.
A call of nag_sum_fft_real_2d (c06pvc) followed by a call of nag_sum_fft_hermitian_2d (c06pwc) will restore the original data.
This function performs multiple one-dimensional discrete Fourier transforms by the fast Fourier transform (FFT) algorithm in Brigham (1974) and Temperton (1983).

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:     mIntegerInput
On entry: $m$, the first dimension of the transform.
Constraint: ${\mathbf{m}}\ge 1$.
2:     nIntegerInput
On entry: $n$, the second dimension of the transform.
Constraint: ${\mathbf{n}}\ge 1$.
3:     x[${\mathbf{m}}×{\mathbf{n}}$]const doubleInput
On entry: the real input dataset $x$, where ${x}_{{j}_{1}{j}_{2}}$is stored in ${\mathbf{x}}\left[{j}_{2}×m+{j}_{1}\right]$, for ${j}_{1}=0,1,\dots ,m-1$ and ${j}_{2}=0,1,\dots ,n-1$.
4:     y[$\left({\mathbf{m}}/2+1\right)×{\mathbf{n}}$]ComplexOutput
On exit: the complex output dataset $\stackrel{^}{z}$, where ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}}$ is stored in ${\mathbf{y}}\left[{k}_{2}×\left(m/2+1\right)+{k}_{1}\right]$ , for ${k}_{1}=0,1,\dots ,m/2$ and ${k}_{2}=0,1,\dots ,n-1$. Note the first dimension is cut roughly by half to remove the redundant information due to conjugate symmetry.
5:     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.
On entry, argument $⟨\mathit{\text{value}}⟩$ had an illegal value.
NE_INT
On entry, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{m}}\ge 1$.
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 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 forward transform using nag_sum_fft_real_2d (c06pvc) and a backward transform using nag_sum_fft_hermitian_2d (c06pwc), and comparing the results with the original sequence (in exact arithmetic they would be identical).

8  Parallelism and Performance

nag_sum_fft_real_2d (c06pvc) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
nag_sum_fft_real_2d (c06pvc) makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.

The time taken by nag_sum_fft_real_2d (c06pvc) is approximately proportional to $mn\mathrm{log}\left(mn\right)$, but also depends on the factors of $m$ and $n$. nag_sum_fft_real_2d (c06pvc) is fastest if the only prime factors of $m$ and $n$ are $2$, $3$ and $5$, and is particularly slow if $m$ or $n$ is a large prime, or has large prime factors.
Workspace is internally allocated by nag_sum_fft_real_2d (c06pvc). The total size of these arrays is approximately proportional to $mn$.

10  Example

This example reads in a bivariate sequence of real data values and prints their discrete Fourier transforms as computed by nag_sum_fft_real_2d (c06pvc). Inverse transforms are then calculated by calling nag_sum_fft_hermitian_2d (c06pwc) showing that the original sequences are restored.

10.1  Program Text

Program Text (c06pvce.c)

10.2  Program Data

Program Data (c06pvce.d)

10.3  Program Results

Program Results (c06pvce.r)