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_hermitian_2d (c06pw)

Purpose

nag_sum_fft_hermitian_2d (c06pw) computes the two-dimensional inverse discrete Fourier transform of a bivariate Hermitian sequence of complex data values.

Syntax

[x, ifail] = c06pw(m, n, y)
[x, ifail] = nag_sum_fft_hermitian_2d(m, n, y)

Description

nag_sum_fft_hermitian_2d (c06pw) computes the two-dimensional inverse discrete Fourier transform of a bivariate Hermitian sequence of complex data values zj1j2zj1j2, for j1 = 0,1,,m1j1=0,1,,m-1 and j2 = 0,1,,n1j2=0,1,,n-1.
The discrete Fourier transform is here defined by
m1
k1 k2 = 1/(sqrt(mn)) j2 = 0n1 z j1 j2 × exp(2πi(( j1 k1 )/m + ( j2 k2 )/n)),
j1 = 0
x^ k1 k2 = 1mn j1=0 m-1 j2=0 n-1 z j1 j2 × exp( 2πi ( j1 k1 m + j2 k2 n ) ) ,
where k1 = 0,1,,m1k1=0,1,,m-1 and k2 = 0,1,,n1k2=0,1,,n-1. (Note the scale factor of 1/(sqrt(mn))1mn in this definition.)
Because the input data satisfies conjugate symmetry (i.e., z k1 k2 z k1 k2  is the complex conjugate of z (mk1) k2 z (m-k1) k2 , the transformed values k1 k2 x^ k1 k2  are real.
A call of nag_sum_fft_real_2d (c06pv) followed by a call of nag_sum_fft_hermitian_2d (c06pw) will restore the original data.
This function performs multiple one-dimensional discrete Fourier transforms by the fast Fourier transform (FFT) algorithm in Brigham (1974) and Temperton (1983).

References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall
Temperton C (1983) Fast mixed-radix real Fourier transforms J. Comput. Phys. 52 340–350

Parameters

Compulsory Input Parameters

1:     m – int64int32nag_int scalar
mm, the first dimension of the transform.
Constraint: m1m1.
2:     n – int64int32nag_int scalar
nn, the second dimension of the transform.
Constraint: n1n1.
3:     y( (m / 2 + 1) × n (m/2+1)×n ) – complex array
The Hermitian sequence of complex input dataset zz, where z j1 j2 z j1 j2  is stored in y( j2 × (m / 2 + 1) + j1) y j2 × ( m/2+1 ) + j1 , for j1 = 0,1,,m / 2j1=0,1,,m/2 and j2 = 0,1,,n1j2=0,1,,n-1. That is, if y is regarded as a two-dimensional array of dimension (0 : m / 2,0 : n1) (0:m/2,0:n-1) , then y(j1,j2) yj1j2  must contain z j1 j2 z j1 j2 .

Optional Input Parameters

None.

Input Parameters Omitted from the MATLAB Interface

None.

Output Parameters

1:     x( m × n m×n ) – double array
The real output dataset x^, where k1 k2 x^ k1 k2 is stored in x( k2 × m + k1)x k2 × m+ k1, for k1 = 0,1,,m1k1=0,1,,m-1 and k2 = 0,1,,n1k2=0,1,,n-1. That is, if x is regarded as a two-dimensional array of dimension (0 : m1,0 : n1) (0:m-1,0:n-1) , then x(k1,k2) xk1k2 contains k1 k2 x^ k1 k2 .
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
Constraint: m1m1.
  ifail = 2ifail=2
Constraint: n1n1.
  ifail = 3ifail=3
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
  ifail = 999ifail=-999
Dynamic memory allocation failed.

Accuracy

Some indication of accuracy can be obtained by performing a forward transform using nag_sum_fft_real_2d (c06pv) and a backward transform using nag_sum_fft_hermitian_2d (c06pw), and comparing the results with the original sequence (in exact arithmetic they would be identical).

Further Comments

The time taken by nag_sum_fft_hermitian_2d (c06pw) is approximately proportional to mn log(mn) mn log(mn) , but also depends on the factors of mm and nn. nag_sum_fft_hermitian_2d (c06pw) is fastest if the only prime factors of mm and nn are 22, 33 and 55, and is particularly slow if mm or nn is a large prime, or has large prime factors.
Workspace is internally allocated by nag_sum_fft_hermitian_2d (c06pw). The total size of these arrays is approximately proportional to mnmn.

Example

function nag_sum_fft_hermitian_2d_example
m = int64(5);
n = int64(2);
x = [0.010;
     1.284;
     1.754;
     0.089;
     1.004;
     0.346;
     1.960;
     0.855;
     0.161;
     1.844];
% Compute Transform
[y, ifail] = nag_sum_fft_real_2d(m, n, x);
fprintf('\nComponents of discrete Fourier transform\n');
% Display as 2-d array
disp(reshape(y, m/2, n));

% Compute Inverse Transform
[x, ifail] = nag_sum_fft_hermitian_2d(m, n, y);
fprintf('Original sequence as restored by inverse transform\n');
% Display as 2-d array
disp(reshape(x, m, n));
 

Components of discrete Fourier transform
   2.9431 + 0.0000i  -0.3241 + 0.0000i
  -0.0235 - 0.5576i  -0.4660 - 0.2298i
  -1.1666 + 0.6359i   0.3624 + 0.2615i

Original sequence as restored by inverse transform
    0.0100    0.3460
    1.2840    1.9600
    1.7540    0.8550
    0.0890    0.1610
    1.0040    1.8440


function c06pw_example
m = int64(5);
n = int64(2);
x = [0.010;
     1.284;
     1.754;
     0.089;
     1.004;
     0.346;
     1.960;
     0.855;
     0.161;
     1.844];
% Compute Transform
[y, ifail] = c06pv(m, n, x);
fprintf('\nComponents of discrete Fourier transform\n');
% Display as 2-d array
disp(reshape(y, m/2, n));

% Compute Inverse Transform
[x, ifail] = c06pw(m, n, y);
fprintf('Original sequence as restored by inverse transform\n');
% Display as 2-d array
disp(reshape(x, m, n));
 

Components of discrete Fourier transform
   2.9431 + 0.0000i  -0.3241 + 0.0000i
  -0.0235 - 0.5576i  -0.4660 - 0.2298i
  -1.1666 + 0.6359i   0.3624 + 0.2615i

Original sequence as restored by inverse transform
    0.0100    0.3460
    1.2840    1.9600
    1.7540    0.8550
    0.0890    0.1610
    1.0040    1.8440



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