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_1d_rfmt (c06fb)

Purpose

nag_sum_fft_hermitian_1d_rfmt (c06fb) calculates the discrete Fourier transform of a Hermitian sequence of nn complex data values (using a work array for extra speed).

Syntax

[x, ifail] = c06fb(x, 'n', n)
[x, ifail] = nag_sum_fft_hermitian_1d_rfmt(x, 'n', n)

Description

Given a Hermitian sequence of nn complex data values zj zj  (i.e., a sequence such that z0 z0  is real and znj z n-j  is the complex conjugate of zj zj , for j = 1,2,,n1j=1,2,,n-1), nag_sum_fft_hermitian_1d_rfmt (c06fb) calculates their discrete Fourier transform defined by
n1
k = 1/(sqrt(n))zj × exp(i(2πjk)/n),  k = 0,1,,n1.
j = 0
x^k = 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.) The transformed values k x^k  are purely real (see also the C06 Chapter Introduction).
To compute the inverse discrete Fourier transform defined by
n1
k = 1/(sqrt(n))zj × exp( + i(2πjk)/n),
j = 0
y^k = 1n j=0 n-1 zj × exp( +i 2πjk n ) ,
this function should be preceded 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_hermitian_1d_rfmt (c06fb) 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.
The sequence to be transformed stored in Hermitian form. If the data values zjzj are written as xj + i yjxj + i yj, and if x is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_fft_hermitian_1d_rfmt (c06fb) is called, then for 0 j n / 20 j n/2, xjxj is contained in x(j)xj, and for 1 j (n1) / 2 1 j (n-1) / 2 , yjyj is contained in x(nj)xn-j. (See also Section [Real transforms] in the C06 Chapter Introduction and Section [Example].)

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 components of the discrete Fourier transform kx^k. If x is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_fft_hermitian_1d_rfmt (c06fb) is called, then kx^k is stored in x(k)xk, for k = 0,1,,n1k=0,1,,n-1.
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_hermitian_1d_rfmt (c06fb) 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_hermitian_1d_rfmt_example
x = [0.34907;
     0.5489;
     0.74776;
     0.94459;
     1.1385;
     1.3285;
     1.5137];
[xOut, ifail] = nag_sum_fft_hermitian_1d_rfmt(x)
 

xOut =

    1.8262
    1.8686
   -0.0175
    0.5020
   -0.5987
   -0.0314
   -2.6256


ifail =

                    0


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

xOut =

    1.8262
    1.8686
   -0.0175
    0.5020
   -0.5987
   -0.0314
   -2.6256


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