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}_{{j}_{1}{j}_{2}\dots {j}_{m}}$, where ${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 ${n}_{1},{n}_{2},\dots ,{n}_{m}$, and the total number of data values is $n={n}_{1}×{n}_{2}×\cdots ×{n}_{m}$.
The discrete Fourier transform is here defined (e.g., for $m=2$) by:
 $z^ k1 , k2 = 1n ∑ j1=0 n1-1 ∑ j2=0 n2-1 z j1j2 × exp -2πi j1k1 n1 + j2k2 n2 ,$
where ${k}_{1}=0,1,\dots ,{n}_{1}-1$, ${k}_{2}=0,1,\dots ,{n}_{2}-1$.
The extension to higher dimensions is obvious. (Note the scale factor of $\frac{1}{\sqrt{n}}$ 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 the complex conjugation of the data values and the transform (by negating the imaginary parts stored in $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 ${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 ${n}_{i}$ (see Arguments).

## References

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

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{nd}\left({\mathbf{ndim}}\right)$int64int32nag_int array
${\mathbf{nd}}\left(\mathit{i}\right)$ must contain ${n}_{\mathit{i}}$ (the dimension of the $\mathit{i}$th variable) , for $\mathit{i}=1,2,\dots ,m$. The largest prime factor of each ${\mathbf{nd}}\left(i\right)$ must not exceed $19$, and the total number of prime factors of ${\mathbf{nd}}\left(i\right)$, counting repetitions, must not exceed $20$.
Constraint: ${\mathbf{nd}}\left(\mathit{i}\right)\ge 1$, for $\mathit{i}=1,2,\dots ,{\mathbf{ndim}}$.
2:     $\mathrm{x}\left({\mathbf{n}}\right)$ – double array
${\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}_{{j}_{1}{j}_{2}\dots {j}_{m}}$, for $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:     $\mathrm{y}\left({\mathbf{n}}\right)$ – double array
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:     $\mathrm{ndim}$int64int32nag_int scalar
Default: the dimension of the array nd.
$m$, the number of dimensions (or variables) in the multivariate data.
Constraint: ${\mathbf{ndim}}\ge 1$.
2:     $\mathrm{n}$int64int32nag_int scalar
Default: the dimension of the arrays x, y. (An error is raised if these dimensions are not equal.)
$n$, the total number of data values.
Constraint: ${\mathbf{n}}={\mathbf{nd}}\left(1\right)×{\mathbf{nd}}\left(2\right)×\cdots ×{\mathbf{nd}}\left({\mathbf{ndim}}\right)$.

### Output Parameters

1:     $\mathrm{x}\left({\mathbf{n}}\right)$ – double array
The real parts of the corresponding elements of the computed transform.
2:     $\mathrm{y}\left({\mathbf{n}}\right)$ – double array
The imaginary parts of the corresponding elements of the computed transform.
3:     $\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{ndim}}<1$.
${\mathbf{ifail}}=2$
 On entry, ${\mathbf{n}}\ne {\mathbf{nd}}\left(1\right)×{\mathbf{nd}}\left(2\right)×\cdots ×{\mathbf{nd}}\left({\mathbf{ndim}}\right)$.
${\mathbf{ifail}}=10×l+1$
At least one of the prime factors of ${\mathbf{nd}}\left(l\right)$ is greater than $19$.
${\mathbf{ifail}}=10×l+2$
${\mathbf{nd}}\left(l\right)$ has more than $20$ prime factors.
${\mathbf{ifail}}=10×l+3$
 On entry, ${\mathbf{nd}}\left(l\right)<1$.
${\mathbf{ifail}}=10×l+4$
 On entry, $\mathit{lwork}<3×{\mathbf{nd}}\left(l\right)$.
${\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 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×\mathrm{log}\left(n\right)$, but also depends on the factorization of the individual dimensions ${\mathbf{nd}}\left(i\right)$. nag_sum_fft_complex_multid_sep (c06fj) 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 bivariate sequence of complex data values and prints the two-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 c06fj_example

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

x = [ 1.000     0.999     0.987     0.936     0.802;
0.994     0.989     0.963     0.891     0.731;
0.903     0.885     0.823     0.694     0.467];
y = [ 0.000    -0.040    -0.159    -0.352    -0.597;
-0.111    -0.151    -0.268    -0.454    -0.682
-0.430    -0.466    -0.568    -0.720    -0.884];
nd = int64(size(x));
l  = int64(2);

% transform, then inverse transform to restore data
[xt, yt, ifail] = c06fj(nd, x, y);
[xr, yr, ifail] = c06fj(nd, xt, -yt);

% Display as complex matrices
z = x + i*y;
zt = reshape(xt+i*yt,nd);
zr = reshape(xr-i*yr,nd);

matrix = 'general';
diag = ' ';
usefrm = 'Above';
format = 'F9.3';
labrow = 'None';
labcol = 'None';
ncols  = int64(80);
indent = int64(0);

title  = 'Original data:';
[ifail] = x04db(...
matrix, diag, z, usefrm, format, title, labrow, labcol, ncols, indent);
disp(' ');
title = 'Discrete Fourier transform of data:';
[ifail] = x04db(...
matrix, diag, zt, usefrm, format, title, labrow, labcol, ncols, indent);
disp(' ');
title = 'Original sequence as restored by inverse transform:';
[ifail] = x04db(...
matrix, diag, zr, usefrm, format, title, labrow, labcol, ncols, indent);

```
```c06fj example results

Original data:
1.000    0.999    0.987    0.936    0.802
0.000   -0.040   -0.159   -0.352   -0.597

0.994    0.989    0.963    0.891    0.731
-0.111   -0.151   -0.268   -0.454   -0.682

0.903    0.885    0.823    0.694    0.467
-0.430   -0.466   -0.568   -0.720   -0.884

Discrete Fourier transform of data:
3.373    0.481    0.251    0.054   -0.419
-1.519   -0.091    0.178    0.319    0.415

0.457    0.055    0.009   -0.022   -0.076
0.137    0.032    0.039    0.036    0.004

-0.170   -0.037   -0.042   -0.038   -0.002
0.493    0.058    0.008   -0.025   -0.083

Original sequence as restored by inverse transform:
1.000    0.999    0.987    0.936    0.802
0.000   -0.040   -0.159   -0.352   -0.597

0.994    0.989    0.963    0.891    0.731
-0.111   -0.151   -0.268   -0.454   -0.682

0.903    0.885    0.823    0.694    0.467
-0.430   -0.466   -0.568   -0.720   -0.884
```