nag_sum_fft_complex_1d_nowork (c06ec) uses the fast Fourier transform (FFT) algorithm (see Brigham (1974)). There are some restrictions on the value of

n

(see Arguments).

References

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

Parameters

Compulsory Input Parameters

1: $x (n)$ – double array: If x is declared with bounds $(0 : n - 1)$ in the function from which nag_sum_fft_complex_1d_nowork (c06ec) is called, then $x (j)$ must contain $x_{j}$ , the real part of $z_{j}$ , for $j = 0, 1, \dots, n - 1$ .
2: $y (n)$ – double array: If y is declared with bounds $(0 : n - 1)$ in the function from which nag_sum_fft_complex_1d_nowork (c06ec) is called, then $y (j)$ must contain $y_{j}$ , the imaginary part of $z_{j}$ , for $j = 0, 1, \dots, n - 1$ .

Optional Input Parameters

1: $n$ – int64int32nag_int scalar: Default: the dimension of the arrays x, y. (An error is raised if these dimensions are not equal.)
$n$ , the number of data values. The largest prime factor of n must not exceed $19$ , and the total number of prime factors of n, counting repetitions, must not exceed $20$ .

Constraint: $n > 1$ .

Output Parameters

1: $x (n)$ – double array: The real parts $a_{k}$ of the components of the discrete Fourier transform. If x is declared with bounds $(0 : n - 1)$ in the function from which nag_sum_fft_complex_1d_nowork (c06ec) is called, then for $0 \leq k \leq n - 1$ , $a_{k}$ is contained in $x (k)$ .
2: $y (n)$ – double array: The imaginary parts $b_{k}$ of the components of the discrete Fourier transform. If y is declared with bounds $(0 : n - 1)$ in the function from which nag_sum_fft_complex_1d_nowork (c06ec) is called, then for $0 \leq k \leq n - 1$ , $b_{k}$ is contained in $y (k)$ .
3: $ifail$ – int64int32nag_int scalar: $ifail = 0$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:

$ifail = 1$: At least one of the prime factors of n is greater than $19$ .

$ifail = 2$: n has more than $20$ prime factors.

$ifail = 3$

On entry,

n \leq 1

$ifail = 4$: An unexpected error has occurred in an internal call. Check all function calls and array dimensions. Seek expert help.

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$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).

Further Comments

The time taken is approximately proportional to

n \times \log (n)

, but also depends on the factorization of

n

. nag_sum_fft_complex_1d_nowork (c06ec) is faster if the only prime factors of

n

are

2

3

5

; and fastest of all if

n

is a power of

2

On the other hand, nag_sum_fft_complex_1d_nowork (c06ec) is particularly slow if

n

has several unpaired prime factors, i.e., if the ‘square-free’ part of

n

has several factors. For such values of

n

, nag_sum_fft_complex_1d_sep (c06fc) (which requires an additional

n

double elements of workspace) is considerably faster.

Example

This example reads in a sequence of complex data values and prints their discrete Fourier transform. It then performs an inverse transform using nag_sum_fft_complex_1d_nowork (c06ec) and nag_sum_conjugate_complex_sep (c06gc), and prints the sequence so obtained alongside the original data values.

Open in the MATLAB editor: c06ec_example

function c06ec_example


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

x_r = [ 0.34907;  0.54890;  0.74776;  0.94459;  1.13850; 1.32850;  1.51370];
x_i = [-0.37168; -0.35669; -0.31175; -0.23702; -0.13274; 0.00074;  0.16298];

z = x_r + i*x_i;
disp('Complex data:');
disp(z);

[x_r, x_i, ifail] = c06ec(x_r, x_i);

z = x_r + i*x_i;
disp('Complex Fourier coeffients:');
disp(z);

x_i = -x_i;
[x_r, x_i, ifail] = c06ec(x_r, x_i);
x_i = -x_i;

z = x_r + i*x_i;
disp('Retrieved complex data:');
disp(z);

c06ec example results

Complex data:
   0.3491 - 0.3717i
   0.5489 - 0.3567i
   0.7478 - 0.3118i
   0.9446 - 0.2370i
   1.1385 - 0.1327i
   1.3285 + 0.0007i
   1.5137 + 0.1630i

Complex Fourier coeffients:
   2.4836 - 0.4710i
  -0.5518 + 0.4968i
  -0.3671 + 0.0976i
  -0.2877 - 0.0586i
  -0.2251 - 0.1748i
  -0.1483 - 0.3084i
   0.0198 - 0.5650i

Retrieved complex data:
   0.3491 - 0.3717i
   0.5489 - 0.3567i
   0.7478 - 0.3117i
   0.9446 - 0.2370i
   1.1385 - 0.1327i
   1.3285 + 0.0007i
   1.5137 + 0.1630i

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox