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_real_1d_rfmt (c06fa)

Purpose

nag_sum_fft_real_1d_rfmt (c06fa) calculates the discrete Fourier transform of a sequence of nn real data values (using a work array for extra speed).

Syntax

[x, ifail] = c06fa(x, 'n', n)
[x, ifail] = nag_sum_fft_real_1d_rfmt(x, 'n', n)

Description

Given a sequence of nn real data values xj xj, for j = 0,1,,n1j=0,1,,n-1, nag_sum_fft_real_1d_rfmt (c06fa) calculates their discrete Fourier transform defined by
n1
k = 1/(sqrt(n))xj × exp(i(2πjk)/n),  k = 0,1,,n1.
j = 0
z^k = 1n j=0 n-1 xj × exp( -i 2πjk n ) ,   k= 0, 1, , n-1 .
(Note the scale factor of 1/(sqrt(n)) 1n  in this definition.) The transformed values k z^k  are complex, but they form a Hermitian sequence (i.e., nk z^ n-k  is the complex conjugate of k z^k ), so they are completely determined by nn real numbers (see also the C06 Chapter Introduction).
To compute the inverse discrete Fourier transform defined by
n1
k = 1/(sqrt(n))xj × exp( + i(2πjk)/n),
j = 0
w^k = 1n j=0 n-1 xj × exp( +i 2πjk n ) ,
this function should be followed by forming the complex conjugates of the k z^k ; that is, x(k) = x(k)x(k)=-x(k), for k = n / 2 + 2,,nk=n/2+2,,n.
nag_sum_fft_real_1d_rfmt (c06fa) 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.
x(j + 1)xj+1 must contain xjxj, for j = 0,1,,n1j=0,1,,n-1.

Optional Input Parameters

1:     n – int64int32nag_int scalar
Default: The dimension of the array x.
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

work

Output Parameters

1:     x(n) – double array
The discrete Fourier transform stored in Hermitian form. If the components of the transform kz^k are written as ak + i bkak + i bk, and if x is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_fft_real_1d_rfmt (c06fa) is called, then for 0 k n / 20 k n/2, akak is contained in x(k)xk, and for 1 k (n1) / 2 1 k (n-1) / 2 , bkbk is contained in x(nk)xn-k. (See also Section [Real transforms] in the C06 Chapter Introduction and Section [Example].)
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
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_real_1d_rfmt (c06fa) 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.

Example

function nag_sum_fft_real_1d_rfmt_example
x = [0.34907;
     0.5489;
     0.74776;
     0.94459;
     1.1385;
     1.3285;
     1.5137];
[xOut, ifail] = nag_sum_fft_real_1d_rfmt(x)
 

xOut =

    2.4836
   -0.2660
   -0.2577
   -0.2564
    0.0581
    0.2030
    0.5309


ifail =

                    0


function c06fa_example
x = [0.34907;
     0.5489;
     0.74776;
     0.94459;
     1.1385;
     1.3285;
     1.5137];
[xOut, ifail] = c06fa(x)
 

xOut =

    2.4836
   -0.2660
   -0.2577
   -0.2564
    0.0581
    0.2030
    0.5309


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