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 xj1j2${x}_{\mathit{j1}\mathit{j2}}$, for j1 = 0,1,,m1$\mathit{j1}=0,1,\dots ,m-1$ and j2 = 0,1,,n1$\mathit{j2}=0,1,\dots ,n-1$.
The discrete Fourier transform is here defined by
 m − 1 ẑ k1 k2 = 1/(sqrt(mn)) ∑ ∑ j2 = 0n − 1 x j1 j2 × exp( − 2πi(( j1 k1 )/m + ( j2 k2 )/n)), j1 = 0
$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 k1 = 0,1,,m1${k}_{1}=0,1,\dots ,m-1$ and k2 = 0,1,,n1${k}_{2}=0,1,\dots ,n-1$. (Note the scale factor of 1/(sqrt(mn))$\frac{1}{\sqrt{mn}}$ in this definition.)
The transformed values k1 k2 ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}}$ are complex. Because of conjugate symmetry (i.e., k1 k2 ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}}$ is the complex conjugate of (mk1) k2 ${\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 performs 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:     m – int64int32nag_int scalar
m$m$, the first dimension of the transform.
Constraint: m1${\mathbf{m}}\ge 1$.
2:     n – int64int32nag_int scalar
n$n$, the second dimension of the transform.
Constraint: n1${\mathbf{n}}\ge 1$.
3:     x( m × n ${\mathbf{m}}×{\mathbf{n}}$) – double array
The real input dataset x$x$, where x j1 j2 ${x}_{\mathit{j1}\mathit{j2}}$is stored in x( j2 × m + j1)${\mathbf{x}}\left(\mathit{j2}×m+\mathit{j1}\right)$, for j1 = 0,1,,m1$\mathit{j1}=0,1,\dots ,m-1$ and j2 = 0,1,,n1$\mathit{j2}=0,1,\dots ,n-1$. That is, if x is regarded as a two-dimensional array of dimension (0 : m1,0 : n1) $\left(0:{\mathbf{m}}-1,0:{\mathbf{n}}-1\right)$, then x(j1,j2) ${\mathbf{x}}\left({j}_{1},{j}_{2}\right)$ must contain x j1 j2 ${x}_{{j}_{1}{j}_{2}}$.

None.

None.

### Output Parameters

1:     y( (m / 2 + 1) × n $\left({\mathbf{m}}/2+1\right)×{\mathbf{n}}$) – complex array
The complex output dataset $\stackrel{^}{z}$, where k1 k2 ${\stackrel{^}{z}}_{\mathit{k1}\mathit{k2}}$ is stored in y( k2 × (m / 2 + 1) + k1)${\mathbf{y}}\left(\mathit{k2}×\left(m/2+1\right)+{k}_{1}\right)$ , for k1 = 0,1,,m / 2$\mathit{k1}=0,1,\dots ,m/2$ and k2 = 0,1,,n1$\mathit{k2}=0,1,\dots ,n-1$. That is, if y is regarded as a two-dimensional array of dimension (0 : m / 2,0 : n1) $\left(0:{\mathbf{m}}/2,0:{\mathbf{n}}-1\right)$, then y(k1,k2) ${\mathbf{y}}\left({k}_{1},{k}_{2}\right)$ contains k1 k2 ${\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:     ifail – int64int32nag_int scalar
${\mathrm{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:
ifail = 1${\mathbf{ifail}}=1$
Constraint: m1${\mathbf{m}}\ge 1$.
ifail = 2${\mathbf{ifail}}=2$
Constraint: n1${\mathbf{n}}\ge 1$.
ifail = 3${\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.
ifail = 999${\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 log(mn) $mn\mathrm{log}\left(mn\right)$, but also depends on the factors of m$m$ and n$n$. nag_sum_fft_real_2d (c06pv) is fastest if the only prime factors of m$m$ and n$n$ are 2$2$, 3$3$ and 5$5$, and is particularly slow if m$m$ or n$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$mn$.

## Example

```function nag_sum_fft_real_2d_example
m = int64(5);
n = int64(2);
x = [0.010;
1.284;
1.754;
0.089;
1.004;
0.346;
1.960;
0.855;
0.161;
1.844];
% Compute Transform
[y, ifail] = nag_sum_fft_real_2d(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] = nag_sum_fft_hermitian_2d(m, n, y);
fprintf('Original sequence as restored by inverse transform\n');
% Display as 2-d array
disp(reshape(x, m, n));
```
```

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

```
```function c06pv_example
m = int64(5);
n = int64(2);
x = [0.010;
1.284;
1.754;
0.089;
1.004;
0.346;
1.960;
0.855;
0.161;
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));
```
```

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

```