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_sep (c06fj)

## Purpose

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

## Syntax

[x, y, ifail] = c06fj(nd, x, y, 'ndim', ndim, 'n', n)
[x, y, ifail] = nag_sum_fft_complex_multid_sep(nd, x, y, 'ndim', ndim, 'n', n)

## Description

nag_sum_fft_complex_multid_sep (c06fj) 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$, k2 = 0 , 1 ,, n21 ${k}_{2}=0,1,\dots ,{n}_{2}-1$.
The extension to higher dimensions is obvious. (Note the scale factor of 1/(sqrt(n)) $\frac{1}{\sqrt{n}}$ in this definition.)
To compute the inverse discrete Fourier transform, defined with exp( + 2πi()) $\mathrm{exp}\left(+2\pi i\left(\dots \right)\right)$ in the above formula instead of exp(2πi()) $\mathrm{exp}\left(-2\pi i\left(\dots \right)\right)$, this function should be preceded and followed by the complex conjugation of the data values and the transform (by negating the imaginary parts stored in y$y$).
The data values must be supplied in a pair of one-dimensional arrays (real and imaginary parts separately), in accordance with the Fortran convention for storing multidimensional data (i.e., with the first subscript j1 ${j}_{1}$ varying most rapidly).
This function calls nag_sum_fft_complex_1d_sep (c06fc) to perform one-dimensional discrete Fourier transforms by the fast Fourier transform (FFT) algorithm in Brigham (1974), and hence there are some restrictions on the values of the ni ${n}_{i}$ (see Section [Parameters]).

## References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall

## Parameters

### Compulsory Input Parameters

1:     nd(ndim) – int64int32nag_int array
ndim, the dimension of the array, must satisfy the constraint ndim1${\mathbf{ndim}}\ge 1$.
nd(i)${\mathbf{nd}}\left(\mathit{i}\right)$ must contain ni${n}_{\mathit{i}}$ (the dimension of the i$\mathit{i}$th variable) , for i = 1,2,,m$\mathit{i}=1,2,\dots ,m$. The largest prime factor of each nd(i)${\mathbf{nd}}\left(i\right)$ must not exceed 19$19$, and the total number of prime factors of nd(i)${\mathbf{nd}}\left(i\right)$, counting repetitions, must not exceed 20$20$.
Constraint: nd(i)1${\mathbf{nd}}\left(\mathit{i}\right)\ge 1$, for i = 1,2,,ndim$\mathit{i}=1,2,\dots ,{\mathbf{ndim}}$.
2:     x(n) – double array
n, the dimension of the array, must satisfy the constraint n = nd(1) × nd(2) × × nd(ndim)${\mathbf{n}}={\mathbf{nd}}\left(1\right)×{\mathbf{nd}}\left(2\right)×\cdots ×{\mathbf{nd}}\left({\mathbf{ndim}}\right)$.
x( 1 + j1 + n1 j2 + n1 n2 j3 + )${\mathbf{x}}\left(1+{j}_{1}+{n}_{1}{j}_{2}+{n}_{1}{n}_{2}{j}_{3}+\dots \right)$ must contain the real part of the complex data value z j1 j2 jm ${z}_{{j}_{1}{j}_{2}\dots {j}_{m}}$, for 0 j1 n1 1 , 0 j2 n21 , $0\le {j}_{1}\le {n}_{1}-1,0\le {j}_{2}\le {n}_{2}-1,\dots \text{}$; i.e., the values are stored in consecutive elements of the array according to the Fortran convention for storing multidimensional arrays.
3:     y(n) – double array
n, the dimension of the array, must satisfy the constraint n = nd(1) × nd(2) × × nd(ndim)${\mathbf{n}}={\mathbf{nd}}\left(1\right)×{\mathbf{nd}}\left(2\right)×\cdots ×{\mathbf{nd}}\left({\mathbf{ndim}}\right)$.
The imaginary parts of the complex data values, stored in the same way as the real parts in the array x.

### 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 arrays x, y. (An error is raised if these dimensions are not equal.)
n$n$, the total number of data values.
Constraint: n = nd(1) × nd(2) × × nd(ndim)${\mathbf{n}}={\mathbf{nd}}\left(1\right)×{\mathbf{nd}}\left(2\right)×\cdots ×{\mathbf{nd}}\left({\mathbf{ndim}}\right)$.

work lwork

### Output Parameters

1:     x(n) – double array
The real parts of the corresponding elements of the computed transform.
2:     y(n) – double array
The imaginary parts of the corresponding elements of the computed transform.
3:     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, n ≠ nd(1) × nd(2) × ⋯ × nd(ndim)${\mathbf{n}}\ne {\mathbf{nd}}\left(1\right)×{\mathbf{nd}}\left(2\right)×\cdots ×{\mathbf{nd}}\left({\mathbf{ndim}}\right)$.
ifail = 10 × l + 1 ${\mathbf{ifail}}=10×l+1$
At least one of the prime factors of nd(l)${\mathbf{nd}}\left(l\right)$ is greater than 19$19$.
ifail = 10 × l + 2 ${\mathbf{ifail}}=10×l+2$
nd(l)${\mathbf{nd}}\left(l\right)$ has more than 20$20$ prime factors.
ifail = 10 × l + 3 ${\mathbf{ifail}}=10×l+3$
 On entry, nd(l) < 1${\mathbf{nd}}\left(l\right)<1$.
ifail = 10 × l + 4 ${\mathbf{ifail}}=10×l+4$
 On entry, lwork < 3 × nd(l)$\mathit{lwork}<3×{\mathbf{nd}}\left(l\right)$.

## 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_sep (c06fj) 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_sep_example
nd = [int64(3);5];
x = [1;
0.994;
0.903;
0.999;
0.989;
0.885;
0.987;
0.963;
0.823;
0.936;
0.891;
0.694;
0.802;
0.731;
0.467];
y = [0;
-0.111;
-0.43;
-0.04;
-0.151;
-0.466;
-0.159;
-0.268;
-0.568;
-0.352;
-0.454;
-0.72;
-0.597;
-0.682;
-0.884];
[xOut, yOut, ifail] = nag_sum_fft_complex_multid_sep(nd, x, y)
```
```

xOut =

3.3731
0.4565
-0.1705
0.4814
0.0549
-0.0375
0.2507
0.0093
-0.0423
0.0543
-0.0217
-0.0377
-0.4194
-0.0759
-0.0022

yOut =

-1.5187
0.1368
0.4927
-0.0907
0.0317
0.0584
0.1776
0.0389
0.0082
0.3188
0.0356
-0.0255
0.4145
0.0045
-0.0829

ifail =

0

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

xOut =

3.3731
0.4565
-0.1705
0.4814
0.0549
-0.0375
0.2507
0.0093
-0.0423
0.0543
-0.0217
-0.0377
-0.4194
-0.0759
-0.0022

yOut =

-1.5187
0.1368
0.4927
-0.0907
0.0317
0.0584
0.1776
0.0389
0.0082
0.3188
0.0356
-0.0255
0.4145
0.0045
-0.0829

ifail =

0

```