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_1d (c06pf)

Purpose

nag_sum_fft_complex_multid_1d (c06pf) computes the discrete Fourier transform of one variable in a multivariate sequence of complex data values.

Syntax

[x, ifail] = c06pf(direct, l, nd, x, 'ndim', ndim, 'n', n)
[x, ifail] = nag_sum_fft_complex_multid_1d(direct, l, nd, x, 'ndim', ndim, 'n', n)

Description

nag_sum_fft_complex_multid_1d (c06pf) computes the discrete Fourier transform of one variable (the llth say) in a multivariate 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 function computes n / nl n/nl  one-dimensional transforms defined by
nl1
j1 kl jm = 1/(sqrt(nl))z j1 jl jm × exp( ± ( 2 π i jl kl )/(nl)),
jl = 0
z^ j1 kl jm = 1nl jl=0 nl-1 z j1 jl jm × exp( ± 2 π i jl kl nl ) ,
where kl = 0 , 1 ,, nl1 kl = 0 , 1 ,, nl-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.
(Note the scale factor of 1/(sqrt(nl)) 1nl  in this definition.)
A call of nag_sum_fft_complex_multid_1d (c06pf) 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 complex 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:     l – int64int32nag_int scalar
ll, the index of the variable (or dimension) on which the discrete Fourier transform is to be performed.
Constraint: 1 l ndim1 l ndim.
3:     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(l)ndl must have less than 3131 prime factors (counting repetitions).
4:     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,l < 1l<1 or l > ndiml>ndim.
  ifail = 3ifail=3
On entry,direct'F'direct'F' or 'B''B'.
  ifail = 4ifail=4
On entry,at least one of the first ndim elements of nd is less than 11.
  ifail = 5ifail=5
On entry,n does not equal the product of the first ndim elements of nd.
  ifail = 6ifail=6
On entry,lwork is too small. The minimum amount of workspace required is returned in work(1)work1.
  ifail = 7ifail=7
On entry,nd(l)ndl has more than 3030 prime factors.
  ifail = 8ifail=8
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 × lognl n×lognl , but also depends on the factorization of nl nl . nag_sum_fft_complex_multid_1d (c06pf) is faster if the only prime factors of nl nl  are 22, 33 or 55; and fastest of all if nl nl  is a power of 22.

Example

function nag_sum_fft_complex_multid_1d_example
direct = 'F';
l = int64(2);
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_1d(direct, l, nd, x)
 

xOut =

   2.1126 - 0.5134i
   2.0429 - 0.7451i
   1.6869 - 1.3721i
   0.2880 - 0.0003i
   0.2862 - 0.0322i
   0.2596 - 0.1246i
   0.1257 + 0.1298i
   0.1389 + 0.1148i
   0.1695 + 0.0631i
  -0.0030 + 0.1899i
   0.0180 + 0.1892i
   0.0791 + 0.1731i
  -0.2873 + 0.1940i
  -0.2633 + 0.2251i
  -0.1759 + 0.2988i


ifail =

                    0


function c06pf_example
direct = 'F';
l = int64(2);
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] = c06pf(direct, l, nd, x)
 

xOut =

   2.1126 - 0.5134i
   2.0429 - 0.7451i
   1.6869 - 1.3721i
   0.2880 - 0.0003i
   0.2862 - 0.0322i
   0.2596 - 0.1246i
   0.1257 + 0.1298i
   0.1389 + 0.1148i
   0.1695 + 0.0631i
  -0.0030 + 0.1899i
   0.0180 + 0.1892i
   0.0791 + 0.1731i
  -0.2873 + 0.1940i
  -0.2633 + 0.2251i
  -0.1759 + 0.2988i


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