hide long namesshow long names
hide short namesshow short names
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_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 j1 j2 jm , where j1 = 0 , 1 ,, n11 ,   j2 = 0 , 1 ,, n21 j1 = 0 , 1 ,, n1-1 ,   j2 = 0 , 1 ,, n2-1 , and so on. Thus the individual dimensions are n1 , n2 ,, nm n1 , n2 ,, nm , and the total number of data values is n = n1 × n2 × × nm n = n1 × n2 ×× nm .
The discrete Fourier transform is here defined (e.g., for m = 2 m=2 ) by:
n11n21
k1 , k2 = 1/(sqrt(n))zj1j2 × exp( ± 2πi((j1k1)/(n1) + (j2k2)/(n2))),
j1 = 0j2 = 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 k1 = 0 , 1 ,, n1-1  and k2 = 0 , 1 ,, n21 k2 = 0 , 1 ,, n2-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)) 1n  in this definition.)
A call of nag_sum_fft_complex_multid (c06pj) with direct = 'F'direct='F' followed by a call with direct = 'B'direct='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 j1  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'direct='F' or 'B''B'.
2:     nd(ndim) – int64int32nag_int array
ndim, the dimension of the array, must satisfy the constraint ndim1ndim1.
The elements of nd must contain the dimensions of the ndim variables; that is, nd(i)ndi must contain the dimension of the iith variable.
Constraints:
  • nd(i)1ndi1, for i = 1,2,,ndimi=1,2,,ndim;
  • nd(i)ndi must have less than 3131 prime factors (counting repetitions), for i = 1,2,,ndimi=1,2,,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 j1 j2 jm  is stored in x( 1 + j1 + n1 j2 + n1 n2 j3 + )x 1 + j1 + n1 j2 + n1 n2 j3 + .

Optional Input Parameters

1:     ndim – int64int32nag_int scalar
Default: The dimension of the array nd.
mm, the number of dimensions (or variables) in the multivariate data.
Constraint: ndim1ndim1.
2:     n – int64int32nag_int scalar
Default: The dimension of the array x.
nn, the total number of data values.
Constraint: n must equal the product of the first ndim elements of the array nd.

Input Parameters Omitted from the MATLAB Interface

work lwork

Output Parameters

1:     x(n) – complex array
The corresponding elements of the computed transform.
2:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
On entry,ndim < 1ndim<1.
  ifail = 2ifail=2
On entry,direct'F'direct'F' or 'B''B'.
  ifail = 3ifail=3
On entry,at least one of the first ndim elements of nd is less than 11.
  ifail = 4ifail=4
On entry,n does not equal the product of the first ndim elements of nd.
  ifail = 5ifail=5
On entry,lwork is too small. The minimum amount of workspace required is returned in work(1)work1.
  ifail = 6ifail=6
On entry,nd(i)ndi has more than 3030 prime factors for some ii.
  ifail = 7ifail=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).

Further Comments

The time taken is approximately proportional to n × log(n) n×log(n) , but also depends on the factorization of the individual dimensions nd(i) ndi . nag_sum_fft_complex_multid (c06pj) is faster if the only prime factors are 22, 33 or 55; and fastest of all if they are powers of 22.

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



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–2013