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_1d_nowork (c06ec)

Purpose

nag_sum_fft_complex_1d_nowork (c06ec) calculates the discrete Fourier transform of a sequence of nn complex data values. (No extra workspace required.)
Note: this function is scheduled to be withdrawn, please see c06ec in Advice on Replacement Calls for Withdrawn/Superseded Routines..

Syntax

[x, y, ifail] = c06ec(x, y, 'n', n)
[x, y, ifail] = nag_sum_fft_complex_1d_nowork(x, y, 'n', n)

Description

Given a sequence of nn complex data values zj zj, for j = 0,1,,n1j=0,1,,n-1, nag_sum_fft_complex_1d_nowork (c06ec) calculates their discrete Fourier transform defined by
n1
k = ak + ibk = 1/(sqrt(n))zj × exp(i(2πjk)/n),  k = 0,1,,n1.
j = 0
z^k = ak + i bk = 1n j=0 n-1 zj × exp( -i 2πjk n ) ,   k= 0, 1, , n-1 .
(Note the scale factor of 1/(sqrt(n)) 1n  in this definition.)
To compute the inverse discrete Fourier transform defined by
n1
k = 1/(sqrt(n))zj × exp( + i(2πjk)/n),
j = 0
w^k = 1n j=0 n-1 zj × exp( +i 2πjk n ) ,
this function should be preceded and followed by calls of nag_sum_conjugate_complex_sep (c06gc) to form the complex conjugates of the zj zj  and the k z^k .
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 nn (see Section [Parameters]).

References

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

Parameters

Compulsory Input Parameters

1:     x(n) – double array
n, the dimension of the array, must satisfy the constraint n > 1n>1.
If x is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_fft_complex_1d_nowork (c06ec) is called, then x(j)xj must contain xjxj, the real part of zjzj, for j = 0,1,,n1j=0,1,,n-1.
2:     y(n) – double array
n, the dimension of the array, must satisfy the constraint n > 1n>1.
If y is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_fft_complex_1d_nowork (c06ec) is called, then y(j)yj must contain yjyj, the imaginary part of zjzj, for j = 0,1,,n1j=0,1,,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.)
nn, the number of data values. The largest prime factor of n must not exceed 1919, and the total number of prime factors of n, counting repetitions, must not exceed 2020.
Constraint: n > 1n>1.

Input Parameters Omitted from the MATLAB Interface

None.

Output Parameters

1:     x(n) – double array
The real parts akak of the components of the discrete Fourier transform. If x is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_fft_complex_1d_nowork (c06ec) is called, then for 0 k n10 k n-1, akak is contained in x(k)xk.
2:     y(n) – double array
The imaginary parts bkbk of the components of the discrete Fourier transform. If y is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_fft_complex_1d_nowork (c06ec) is called, then for 0kn10kn-1, bkbk is contained in y(k)yk.
3:     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
At least one of the prime factors of n is greater than 1919.
  ifail = 2ifail=2
n has more than 2020 prime factors.
  ifail = 3ifail=3
On entry,n1n1.
  ifail = 4ifail=4
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 nn. nag_sum_fft_complex_1d_nowork (c06ec) is faster if the only prime factors of nn are 22, 33 or 55; and fastest of all if nn is a power of 22.
On the other hand, nag_sum_fft_complex_1d_nowork (c06ec) is particularly slow if nn has several unpaired prime factors, i.e., if the ‘square-free’ part of nn has several factors. For such values of nn, nag_sum_fft_complex_1d_sep (c06fc) (which requires an additional nn double elements of workspace) is considerably faster.

Example

function nag_sum_fft_complex_1d_nowork_example
x = [0.34907;
     0.5489;
     0.74776;
     0.94459;
     1.1385;
     1.3285;
     1.5137];
y = [-0.37168;
     -0.35669;
     -0.31175;
     -0.23702;
     -0.13274;
     0.00074;
     0.16298];
[xOut, yOut, ifail] = nag_sum_fft_complex_1d_nowork(x, y)
 

xOut =

    2.4836
   -0.5518
   -0.3671
   -0.2877
   -0.2251
   -0.1483
    0.0198


yOut =

   -0.4710
    0.4968
    0.0976
   -0.0586
   -0.1748
   -0.3084
   -0.5650


ifail =

                    0


function c06ec_example
x = [0.34907;
     0.5489;
     0.74776;
     0.94459;
     1.1385;
     1.3285;
     1.5137];
y = [-0.37168;
     -0.35669;
     -0.31175;
     -0.23702;
     -0.13274;
     0.00074;
     0.16298];
[xOut, yOut, ifail] = c06ec(x, y)
 

xOut =

    2.4836
   -0.5518
   -0.3671
   -0.2877
   -0.2251
   -0.1483
    0.0198


yOut =

   -0.4710
    0.4968
    0.0976
   -0.0586
   -0.1748
   -0.3084
   -0.5650


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