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_complex_multid (c06pj)

## Purpose

nag_sum_fft_complex_multid (c06pj) computes the multidimensional discrete Fourier transform of a multivariate sequence of complex data values.

## Syntax

[x, ifail] = c06pj(direct, nd, x, 'ndim', ndim, 'n', n)
[x, ifail] = nag_sum_fft_complex_multid(direct, nd, x, 'ndim', ndim, 'n', n)

## Description

nag_sum_fft_complex_multid (c06pj) computes the multidimensional discrete Fourier transform of a multidimensional sequence of complex data values z j1 j2 jm ${z}_{{j}_{1}{j}_{2}\dots {j}_{m}}$, where j1 = 0 , 1 ,, n11 ,   j2 = 0 , 1 ,, n21 ${j}_{1}=0,1,\dots ,{n}_{1}-1\text{, }{j}_{2}=0,1,\dots ,{n}_{2}-1$, and so on. Thus the individual dimensions are n1 , n2 ,, nm ${n}_{1},{n}_{2},\dots ,{n}_{m}$, and the total number of data values is n = n1 × n2 × × nm $n={n}_{1}×{n}_{2}×\cdots ×{n}_{m}$.
The discrete Fourier transform is here defined (e.g., for m = 2 $m=2$) by:
 n1 − 1 n2 − 1 ẑ k1 , k2 = 1/(sqrt(n)) ∑ ∑ zj1j2 × exp( ± 2πi((j1k1)/(n1) + (j2k2)/(n2))), j1 = 0 j2 = 0
$z^ k1 , k2 = 1n ∑ j1=0 n1-1 ∑ j2=0 n2-1 z j1j2 × exp( ±2πi ( j1k1 n1 + j2k2 n2 ) ) ,$
where k1 = 0 , 1 ,, n11 ${k}_{1}=0,1,\dots ,{n}_{1}-1$ and k2 = 0 , 1 ,, n21 ${k}_{2}=0,1,\dots ,{n}_{2}-1$. The plus or minus sign in the argument of the exponential terms in the above definition determine the direction of the transform: a minus sign defines the forward direction and a plus sign defines the backward direction.
The extension to higher dimensions is obvious. (Note the scale factor of 1/(sqrt(n)) $\frac{1}{\sqrt{n}}$ in this definition.)
A call of nag_sum_fft_complex_multid (c06pj) with direct = 'F'${\mathbf{direct}}=\text{'F'}$ followed by a call with direct = 'B'${\mathbf{direct}}=\text{'B'}$ will restore the original data.
The data values must be supplied in a one-dimensional array using column-major storage ordering of multidimensional data (i.e., with the first subscript j1 ${j}_{1}$ varying most rapidly).
This function calls nag_sum_fft_complex_1d_multi_row (c06pr) to perform one-dimensional discrete Fourier transforms. Hence, the function uses a variant of the fast Fourier transform (FFT) algorithm (see Brigham (1974)) known as the Stockham self-sorting algorithm, which is described in Temperton (1983).

## 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:     direct – string (length ≥ 1)
If the forward transform as defined in Section [Description] is to be computed, then direct must be set equal to 'F'.
If the backward transform is to be computed then direct must be set equal to 'B'.
Constraint: direct = 'F'${\mathbf{direct}}=\text{'F'}$ or 'B'$\text{'B'}$.
2:     nd(ndim) – int64int32nag_int array
ndim, the dimension of the array, must satisfy the constraint ndim1${\mathbf{ndim}}\ge 1$.
The elements of nd must contain the dimensions of the ndim variables; that is, nd(i)${\mathbf{nd}}\left(i\right)$ must contain the dimension of the i$i$th variable.
Constraints:
• nd(i)1${\mathbf{nd}}\left(\mathit{i}\right)\ge 1$, for i = 1,2,,ndim$\mathit{i}=1,2,\dots ,{\mathbf{ndim}}$;
• nd(i)${\mathbf{nd}}\left(\mathit{i}\right)$ must have less than 31$31$ prime factors (counting repetitions), for i = 1,2,,ndim$\mathit{i}=1,2,\dots ,{\mathbf{ndim}}$.
3:     x(n) – complex array
n, the dimension of the array, must satisfy the constraint n must equal the product of the first ndim elements of the array nd.
The complex data values. Data values are stored in x using column-major ordering for storing multidimensional arrays; that is, z j1 j2 jm ${z}_{{j}_{1}{j}_{2}\cdots {j}_{m}}$ is stored in x( 1 + j1 + n1 j2 + n1 n2 j3 + )${\mathbf{x}}\left(1+{j}_{1}+{n}_{1}{j}_{2}+{n}_{1}{n}_{2}{j}_{3}+\cdots \right)$.

### Optional Input Parameters

1:     ndim – int64int32nag_int scalar
Default: The dimension of the array nd.
m$m$, the number of dimensions (or variables) in the multivariate data.
Constraint: ndim1${\mathbf{ndim}}\ge 1$.
2:     n – int64int32nag_int scalar
Default: The dimension of the array x.
n$n$, the total number of data values.
Constraint: n must equal the product of the first ndim elements of the array nd.

work lwork

### Output Parameters

1:     x(n) – complex array
The corresponding elements of the computed transform.
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$
 On entry, ndim < 1${\mathbf{ndim}}<1$.
ifail = 2${\mathbf{ifail}}=2$
 On entry, direct ≠ 'F'${\mathbf{direct}}\ne \text{'F'}$ or 'B'$\text{'B'}$.
ifail = 3${\mathbf{ifail}}=3$
 On entry, at least one of the first ndim elements of nd is less than 1$1$.
ifail = 4${\mathbf{ifail}}=4$
 On entry, n does not equal the product of the first ndim elements of nd.
ifail = 5${\mathbf{ifail}}=5$
 On entry, lwork is too small. The minimum amount of workspace required is returned in work(1)$\mathit{work}\left(1\right)$.
ifail = 6${\mathbf{ifail}}=6$
 On entry, nd(i)${\mathbf{nd}}\left(i\right)$ has more than 30$30$ prime factors for some i$i$.
ifail = 7${\mathbf{ifail}}=7$
An unexpected error has occurred in an internal call. Check all function calls and array dimensions. Seek expert help.

## 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 n × log(n) $n×\mathrm{log}\left(n\right)$, but also depends on the factorization of the individual dimensions nd(i) ${\mathbf{nd}}\left(i\right)$. nag_sum_fft_complex_multid (c06pj) is faster if the only prime factors are 2$2$, 3$3$ or 5$5$; and fastest of all if they are powers of 2$2$.

## Example

```function nag_sum_fft_complex_multid_example
direct = 'F';
nd = [int64(3);5];
x = [1;
0.994 - 0.111i;
0.903 - 0.43i;
0.999 - 0.04i;
0.989 - 0.151i;
0.885 - 0.466i;
0.987 - 0.159i;
0.963 - 0.268i;
0.823 - 0.568i;
0.936 - 0.352i;
0.891 - 0.454i;
0.694 - 0.72i;
0.802 - 0.597i;
0.731 - 0.682i;
0.467 - 0.884i];
[xOut, ifail] = nag_sum_fft_complex_multid(direct, nd, x)
```
```

xOut =

3.3731 - 1.5187i
0.4565 + 0.1368i
-0.1705 + 0.4927i
0.4814 - 0.0907i
0.0549 + 0.0317i
-0.0375 + 0.0584i
0.2507 + 0.1776i
0.0093 + 0.0389i
-0.0423 + 0.0082i
0.0543 + 0.3188i
-0.0217 + 0.0356i
-0.0377 - 0.0255i
-0.4194 + 0.4145i
-0.0759 + 0.0045i
-0.0022 - 0.0829i

ifail =

0

```
```function c06pj_example
direct = 'F';
nd = [int64(3);5];
x = [1;
0.994 - 0.111i;
0.903 - 0.43i;
0.999 - 0.04i;
0.989 - 0.151i;
0.885 - 0.466i;
0.987 - 0.159i;
0.963 - 0.268i;
0.823 - 0.568i;
0.936 - 0.352i;
0.891 - 0.454i;
0.694 - 0.72i;
0.802 - 0.597i;
0.731 - 0.682i;
0.467 - 0.884i];
[xOut, ifail] = c06pj(direct, nd, x)
```
```

xOut =

3.3731 - 1.5187i
0.4565 + 0.1368i
-0.1705 + 0.4927i
0.4814 - 0.0907i
0.0549 + 0.0317i
-0.0375 + 0.0584i
0.2507 + 0.1776i
0.0093 + 0.0389i
-0.0423 + 0.0082i
0.0543 + 0.3188i
-0.0217 + 0.0356i
-0.0377 - 0.0255i
-0.4194 + 0.4145i
-0.0759 + 0.0045i
-0.0022 - 0.0829i

ifail =

0

```