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

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_sum_fft_complex_3d_sep (c06fx)

## Purpose

nag_sum_fft_complex_3d_sep (c06fx) computes the three-dimensional discrete Fourier transform of a trivariate sequence of complex data values. This function is designed to be particularly efficient on vector processors.

## Syntax

[x, y, trign1, trign2, trign3, ifail] = c06fx(n1, n2, n3, x, y, init, trign1, trign2, trign3)
[x, y, trign1, trign2, trign3, ifail] = nag_sum_fft_complex_3d_sep(n1, n2, n3, x, y, init, trign1, trign2, trign3)

## Description

nag_sum_fft_complex_3d_sep (c06fx) computes the three-dimensional discrete Fourier transform of a trivariate sequence of complex data values ${z}_{{j}_{1}{j}_{2}{j}_{3}}$, for $\mathit{j1}=0,1,\dots ,{n}_{1}-1$, $\mathit{j2}=0,1,\dots ,{n}_{2}-1$ and $\mathit{j3}=0,1,\dots ,{n}_{3}-1$.
The discrete Fourier transform is here defined by
 $z^ k1 k2 k3 = 1 n1 n2 n3 ∑ j1=0 n1-1 ∑ j2=0 n2-1 ∑ j3=0 n3-1 z j1 j2 j3 × exp -2πi j1k1 n1 + j2k2 n2 + j3k3 n3 ,$
where ${k}_{1}=0,1,\dots ,{n}_{1}-1$, ${k}_{2}=0,1,\dots ,{n}_{2}-1$, ${k}_{3}=0,1,\dots ,{n}_{3}-1$.
(Note the scale factor of $\frac{1}{\sqrt{{n}_{1}{n}_{2}{n}_{3}}}$ in this definition.)
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 forming the complex conjugates of the data values and the transform.
This function performs, for each dimension, multiple one-dimensional discrete Fourier transforms by the fast Fourier transform (FFT) algorithm (see Brigham (1974)). It is designed to be particularly efficient on vector processors.

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

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{n1}$int64int32nag_int scalar
${n}_{1}$, the first dimension of the transform.
Constraint: ${\mathbf{n1}}\ge 1$.
2:     $\mathrm{n2}$int64int32nag_int scalar
${n}_{2}$, the second dimension of the transform.
Constraint: ${\mathbf{n2}}\ge 1$.
3:     $\mathrm{n3}$int64int32nag_int scalar
${n}_{3}$, the third dimension of the transform.
Constraint: ${\mathbf{n3}}\ge 1$.
4:     $\mathrm{x}\left({\mathbf{n1}}×{\mathbf{n2}}×{\mathbf{n3}}\right)$ – double array
5:     $\mathrm{y}\left({\mathbf{n1}}×{\mathbf{n2}}×{\mathbf{n3}}\right)$ – double array
The real and imaginary parts of the complex data values must be stored in arrays x and y respectively. If x and y are regarded as three-dimensional arrays of dimension $\left(0:{\mathbf{n1}}-1,0:{\mathbf{n2}}-1,0:{\mathbf{n3}}-1\right)$, then ${\mathbf{x}}\left({j}_{1},{j}_{2},{j}_{3}\right)$ and ${\mathbf{y}}\left({j}_{1},{j}_{2},{j}_{3}\right)$ must contain the real and imaginary parts of ${z}_{{j}_{1}{j}_{2}{j}_{3}}$.
6:     $\mathrm{init}$ – string (length ≥ 1)
Indicates whether trigonometric coefficients are to be calculated.
${\mathbf{init}}=\text{'I'}$
Calculate the required trigonometric coefficients for the given values of ${n}_{1}$, ${n}_{2}$ and ${n}_{3}$, and store in the corresponding arrays trign1, trign2 and trign3.
${\mathbf{init}}=\text{'S'}$ or $\text{'R'}$
The required trigonometric coefficients are assumed to have been calculated and stored in the arrays trign1, trign2 and trign3 in a prior call to nag_sum_fft_complex_3d_sep (c06fx). The function performs a simple check that the current values of ${n}_{1}$, ${n}_{2}$ and ${n}_{3}$ are consistent with the corresponding values stored in trign1, trign2 and trign3.
Constraint: ${\mathbf{init}}=\text{'I'}$, $\text{'S'}$ or $\text{'R'}$.
7:     $\mathrm{trign1}\left(2×{\mathbf{n1}}\right)$ – double array
8:     $\mathrm{trign2}\left(2×{\mathbf{n2}}\right)$ – double array
9:     $\mathrm{trign3}\left(2×{\mathbf{n3}}\right)$ – double array
If ${\mathbf{init}}=\text{'S'}$ or $\text{'R'}$, trign1, trign2 and trign3 must contain the required coefficients calculated in a previous call of the function. Otherwise trign1, trign2 and trign3 need not be set. If ${\mathbf{n1}}={\mathbf{n2}}$, the same array may be supplied for trign1 and trign2. Similar considerations apply if ${\mathbf{n2}}={\mathbf{n3}}$ or ${\mathbf{n1}}={\mathbf{n3}}$.

None.

### Output Parameters

1:     $\mathrm{x}\left({\mathbf{n1}}×{\mathbf{n2}}×{\mathbf{n3}}\right)$ – double array
2:     $\mathrm{y}\left({\mathbf{n1}}×{\mathbf{n2}}×{\mathbf{n3}}\right)$ – double array
The real and imaginary parts respectively of the corresponding elements of the computed transform.
3:     $\mathrm{trign1}\left(2×{\mathbf{n1}}\right)$ – double array
4:     $\mathrm{trign2}\left(2×{\mathbf{n2}}\right)$ – double array
5:     $\mathrm{trign3}\left(2×{\mathbf{n3}}\right)$ – double array
trign1, trign2 and trign3 contain the required coefficients (computed by the function if ${\mathbf{init}}=\text{'I'}$).
6:     $\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$
 On entry, ${\mathbf{n1}}<1$.
${\mathbf{ifail}}=2$
 On entry, ${\mathbf{n2}}<1$.
${\mathbf{ifail}}=3$
 On entry, ${\mathbf{n3}}<1$.
${\mathbf{ifail}}=4$
 On entry, ${\mathbf{init}}\ne \text{'I'}$, $\text{'S'}$ or $\text{'R'}$.
${\mathbf{ifail}}=5$
Not used at this Mark.
${\mathbf{ifail}}=6$
 On entry, ${\mathbf{init}}=\text{'S'}$ or $\text{'R'}$, but at least one of the arrays trign1, trign2 and trign3 is inconsistent with the current value of n1, n2 or n3.
${\mathbf{ifail}}=7$
An unexpected error has occurred in an internal call. Check all function calls and array dimensions. Seek expert help.
${\mathbf{ifail}}=-99$
An unexpected error has been triggered by this routine. Please contact NAG.
${\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 subsequent inverse transform and comparing the results with the original sequence (in exact arithmetic they would be identical).

## Further Comments

The time taken is approximately proportional to ${n}_{1}{n}_{2}{n}_{3}×\mathrm{log}\left({n}_{1}{n}_{2}{n}_{3}\right)$, but also depends on the factorization of the individual dimensions ${n}_{1}$, ${n}_{2}$ and ${n}_{3}$. nag_sum_fft_complex_3d_sep (c06fx) is faster if the only prime factors are $2$, $3$ or $5$; and fastest of all if they are powers of $2$.

## Example

This example reads in a trivariate sequence of complex data values and prints the three-dimensional Fourier transform. It then performs an inverse transform and prints the sequence so obtained, which may be compared to the original data values.
function c06fx_example

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

x = cat(3,[ 1.000  0.994  0.903;
0.500  0.494  0.403],...
[ 0.999  0.989  0.885;
0.499  0.489  0.385],...
[ 0.987  0.963  0.823;
0.487  0.463  0.323],...
[ 0.936  0.891  0.694;
0.436  0.391  0.194]);
y = cat(3,[ 0.000 -0.111 -0.430;
0.500  0.111  0.430],...
[-0.040 -0.151 -0.466;
0.040  0.151  0.466],...
[-0.159 -0.268 -0.568;
0.159  0.268  0.568],...
[-0.352 -0.454 -0.720;
0.352  0.454  0.720]);

nd = int64(size(x));

n1 = nd(1);
n2 = nd(2);
n3 = nd(3);

% Transform
init = 'Initial';
trign1 = zeros(2*n1,1);
trign2 = zeros(2*n2,1);
trign3 = zeros(2*n3,1);
[xt, yt, trign1, trign2, trign3, ifail] = ...
c06fx(...
n1, n2, n3, x, y, init, trign1, trign2, trign3);

% Restore
init = 'Subsequent';
[xr, yr, trign1, trign2, trign3, ifail] = ...
c06fx(...
n1, n2, n3, xt, -yt, init, trign1, trign2, trign3);

disp('Original Data:');
z = x + i*y;
disp(z);

disp('Components of discrete Fourier transform:');
zt = reshape(xt + i*yt,nd);
disp(zt);

disp('Original sequence as restored by inverse transform');
zr = reshape(xr + i*yr,nd);
disp(zr);

c06fx example results

Original Data:

(:,:,1) =

1.0000 + 0.0000i   0.9940 - 0.1110i   0.9030 - 0.4300i
0.5000 + 0.5000i   0.4940 + 0.1110i   0.4030 + 0.4300i

(:,:,2) =

0.9990 - 0.0400i   0.9890 - 0.1510i   0.8850 - 0.4660i
0.4990 + 0.0400i   0.4890 + 0.1510i   0.3850 + 0.4660i

(:,:,3) =

0.9870 - 0.1590i   0.9630 - 0.2680i   0.8230 - 0.5680i
0.4870 + 0.1590i   0.4630 + 0.2680i   0.3230 + 0.5680i

(:,:,4) =

0.9360 - 0.3520i   0.8910 - 0.4540i   0.6940 - 0.7200i
0.4360 + 0.3520i   0.3910 + 0.4540i   0.1940 + 0.7200i

Components of discrete Fourier transform:

(:,:,1) =

3.2921 + 0.1021i   0.1433 - 0.0860i   0.1433 + 0.2902i
1.2247 - 1.6203i   0.4243 + 0.3197i  -0.4243 + 0.3197i

(:,:,2) =

0.0506 - 0.0416i   0.0155 + 0.1527i  -0.0502 + 0.1180i
0.3548 + 0.0833i   0.0204 - 0.1147i   0.0070 - 0.0800i

(:,:,3) =

0.1127 + 0.1021i  -0.0245 + 0.1268i  -0.0245 + 0.0773i
-0.0000 + 0.1621i   0.0134 - 0.0914i  -0.0134 - 0.0914i

(:,:,4) =

0.0506 + 0.2458i  -0.0502 + 0.0861i   0.0155 + 0.0515i
-0.3548 + 0.0833i  -0.0070 - 0.0800i  -0.0204 - 0.1147i

Original sequence as restored by inverse transform

(:,:,1) =

1.0000 - 0.0000i   0.9940 + 0.1110i   0.9030 + 0.4300i
0.5000 - 0.5000i   0.4940 - 0.1110i   0.4030 - 0.4300i

(:,:,2) =

0.9990 + 0.0400i   0.9890 + 0.1510i   0.8850 + 0.4660i
0.4990 - 0.0400i   0.4890 - 0.1510i   0.3850 - 0.4660i

(:,:,3) =

0.9870 + 0.1590i   0.9630 + 0.2680i   0.8230 + 0.5680i
0.4870 - 0.1590i   0.4630 - 0.2680i   0.3230 - 0.5680i

(:,:,4) =

0.9360 + 0.3520i   0.8910 + 0.4540i   0.6940 + 0.7200i
0.4360 - 0.3520i   0.3910 - 0.4540i   0.1940 - 0.7200i

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015