c06fj:: Summation of Series (NAG Toolbox)

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, 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} \times n_{2} \times \dots \times n_{m}

The discrete Fourier transform is here defined (e.g., for

m = 2

) by:

{\hat{z}}_{k_{1}, k_{2}} = \frac{1}{\sqrt{n}} \sum_{j_{1} = 0}^{n_{1} - 1} \sum_{j_{2} = 0}^{n_{2} - 1} z_{j_{1} j_{2}} \times \exp (- 2 π i (\frac{j_{1} k_{1}}{n_{1}} + \frac{j_{2} k_{2}}{n_{2}})),

where

k_{1} = 0, 1, \dots, n_{1} - 1

k_{2} = 0, 1, \dots, n_{2} - 1

To compute the inverse discrete Fourier transform, defined with

\exp (+ 2 π i (\dots))

in the above formula instead of

\exp (- 2 π i (\dots))

, 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

Parameters

Compulsory Input Parameters

Optional Input Parameters

Output Parameters

Error Indicators and Warnings

Accuracy

Further Comments

The time taken is approximately proportional to

n \times \log (n)

, but also depends on the factorization of the individual dimensions

nd (i)

. nag_sum_fft_complex_multid_sep (c06fj) is faster if the only prime factors are

2

3

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

NAG Toolbox: nag_sum_fft_complex_multid_sep (c06fj)

▸▿ Contents

Purpose

Syntax

Description