Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_sum_fft_real_2d (c06pv)

## Purpose

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

## Syntax

[y, ifail] = c06pv(m, n, x)
[y, ifail] = nag_sum_fft_real_2d(m, n, x)

## Description

nag_sum_fft_real_2d (c06pv) computes the two-dimensional discrete Fourier transform of a bivariate sequence of real data values ${x}_{\mathit{j1}\mathit{j2}}$, for $\mathit{j1}=0,1,\dots ,m-1$ and $\mathit{j2}=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 (c06pv) followed by a call of nag_sum_fft_hermitian_2d (c06pw) will restore the original data.
This function calls nag_sum_fft_realherm_1d_multi_col (c06pq) and nag_sum_fft_complex_1d_multi_row (c06pr) to perform multiple one-dimensional discrete Fourier transforms by the fast Fourier transform (FFT) algorithm in Brigham (1974) and Temperton (1983).

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

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{m}$int64int32nag_int scalar
$m$, the first dimension of the transform.
Constraint: ${\mathbf{m}}\ge 1$.
2:     $\mathrm{n}$int64int32nag_int scalar
$n$, the second dimension of the transform.
Constraint: ${\mathbf{n}}\ge 1$.
3:     $\mathrm{x}\left({\mathbf{m}}×{\mathbf{n}}\right)$ – double array
The real input dataset $x$, where ${x}_{\mathit{j1}\mathit{j2}}$is stored in ${\mathbf{x}}\left(\mathit{j2}×m+\mathit{j1}\right)$, for $\mathit{j1}=0,1,\dots ,m-1$ and $\mathit{j2}=0,1,\dots ,n-1$. That is, if x is regarded as a two-dimensional array of dimension $\left(0:{\mathbf{m}}-1,0:{\mathbf{n}}-1\right)$, then ${\mathbf{x}}\left({j}_{1},{j}_{2}\right)$ must contain ${x}_{{j}_{1}{j}_{2}}$.

None.

### Output Parameters

1:     $\mathrm{y}\left(\left({\mathbf{m}}/2+1\right)×{\mathbf{n}}\right)$ – complex array
The complex output dataset $\stackrel{^}{z}$, where ${\stackrel{^}{z}}_{\mathit{k1}\mathit{k2}}$ is stored in ${\mathbf{y}}\left(\mathit{k2}×\left(m/2+1\right)+{k}_{1}\right)$ , for $\mathit{k1}=0,1,\dots ,m/2$ and $\mathit{k2}=0,1,\dots ,n-1$. That is, if y is regarded as a two-dimensional array of dimension $\left(0:{\mathbf{m}}/2,0:{\mathbf{n}}-1\right)$, then ${\mathbf{y}}\left({k}_{1},{k}_{2}\right)$ contains ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}}$. Note the first dimension is cut roughly by half to remove the redundant information due to conjugate symmetry.
2:     $\mathrm{ifail}$int64int32nag_int scalar
${\mathbf{ifail}}={\mathbf{0}}$ unless the function detects an error (see Error Indicators and Warnings).

## Error Indicators and Warnings

Errors or warnings detected by the function:
${\mathbf{ifail}}=1$
Constraint: ${\mathbf{m}}\ge 1$.
${\mathbf{ifail}}=2$
Constraint: ${\mathbf{n}}\ge 1$.
${\mathbf{ifail}}=3$
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.
${\mathbf{ifail}}=-99$
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

## Accuracy

Some indication of accuracy can be obtained by performing a forward transform using nag_sum_fft_real_2d (c06pv) and a backward transform using nag_sum_fft_hermitian_2d (c06pw), and comparing the results with the original sequence (in exact arithmetic they would be identical).

The time taken by nag_sum_fft_real_2d (c06pv) 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 (c06pv) 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 (c06pv). The total size of these arrays is approximately proportional to $mn$.

## 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 (c06pv). Inverse transforms are then calculated by calling nag_sum_fft_hermitian_2d (c06pw) showing that the original sequences are restored.
```function c06pv_example

fprintf('c06pv example results\n\n');

m = int64(5);
n = int64(2);
x = [0.010  0.346;
1.284  1.960;
1.754  0.855;
0.089  0.161;
1.004  1.844];

% Compute Transform
[y, ifail] = c06pv(m, n, x);
fprintf('\nComponents of discrete Fourier transform\n');
% Display as 2-d array
disp(reshape(y, m/2, n));

% Compute Inverse Transform
[x, ifail] = c06pw(m, n, y);
fprintf('Original sequence as restored by inverse transform\n');
% Display as 2-d array
disp(reshape(x, m, n));

```
```c06pv example results

Components of discrete Fourier transform
2.9431 + 0.0000i  -0.3241 + 0.0000i
-0.0235 - 0.5576i  -0.4660 - 0.2298i
-1.1666 + 0.6359i   0.3624 + 0.2615i

Original sequence as restored by inverse transform
0.0100    0.3460
1.2840    1.9600
1.7540    0.8550
0.0890    0.1610
1.0040    1.8440

```