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_realherm_1d (c06pa)

Purpose

nag_sum_fft_realherm_1d (c06pa) calculates the discrete Fourier transform of a sequence of n$n$ real data values or of a Hermitian sequence of n$n$ complex data values stored in compact form in a double array.

Syntax

[x, ifail] = c06pa(direct, x, n)
[x, ifail] = nag_sum_fft_realherm_1d(direct, x, n)

Description

Given a sequence of n$n$ real data values xj ${x}_{\mathit{j}}$, for j = 0,1,,n1$\mathit{j}=0,1,\dots ,n-1$, nag_sum_fft_realherm_1d (c06pa) calculates their discrete Fourier transform (in the Forward direction) defined by
 n − 1 ẑk = 1/(sqrt(n)) ∑ xj × exp( − i(2πjk)/n),  k = 0,1, … ,n − 1. j = 0
$z^k = 1n ∑ j=0 n-1 xj × exp( -i 2πjk n ) , k= 0, 1, …, n-1 .$
The transformed values k ${\stackrel{^}{z}}_{k}$ are complex, but they form a Hermitian sequence (i.e., nk ${\stackrel{^}{z}}_{n-k}$ is the complex conjugate of k ${\stackrel{^}{z}}_{k}$), so they are completely determined by n$n$ real numbers (since 0 ${\stackrel{^}{z}}_{0}$ is real, as is n / 2 ${\stackrel{^}{z}}_{n/2}$ for n$n$ even).
Alternatively, given a Hermitian sequence of n$n$ complex data values zj ${z}_{j}$, this function calculates their inverse (backward) discrete Fourier transform defined by
 n − 1 x̂k = 1/(sqrt(n)) ∑ zj × exp(i(2πjk)/n),  k = 0,1, … ,n − 1. j = 0
$x^k = 1n ∑ j=0 n-1 zj × exp( i 2πjk n ) , k= 0, 1, …, n-1 .$
The transformed values k ${\stackrel{^}{x}}_{k}$ are real.
(Note the scale factor of 1/(sqrt(n)) $\frac{1}{\sqrt{n}}$ in the above definitions.)
A call of nag_sum_fft_realherm_1d (c06pa) with direct = 'F'${\mathbf{direct}}=\text{'F'}$ followed by a call with direct = 'B'${\mathbf{direct}}=\text{'B'}$ will restore the original data.
nag_sum_fft_realherm_1d (c06pa) uses a variant of the fast Fourier transform (FFT) algorithm (see Brigham (1974)) known as the Stockham self-sorting algorithm, which is described in Temperton (1983).
The same functionality is available using the forward and backward transform function pair: nag_sum_fft_real_2d (c06pv) and nag_sum_fft_hermitian_2d (c06pw) on setting n = 1${\mathbf{n}}=1$. This pair use a different storage solution; real data is stored in a double array, while Hermitian data (the first unconjugated half) is stored in a complex array.

References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall
Temperton C (1983) Self-sorting mixed-radix fast Fourier transforms J. Comput. Phys. 52 1–23

Parameters

Compulsory Input Parameters

1:     direct – string (length ≥ 1)
If the forward transform as defined in Section [Description] is to be computed, then direct must be set equal to 'F'.
If the backward transform is to be computed then direct must be set equal to 'B'.
Constraint: direct = 'F'${\mathbf{direct}}=\text{'F'}$ or 'B'$\text{'B'}$.
2:     x( n + 2 ${\mathbf{n}}+2$) – double array
If x is declared with bounds (0 : n + 1)$\left(0:{\mathbf{n}}+1\right)$ in the function from which nag_sum_fft_realherm_1d (c06pa) is called, then:
• if direct = 'F'${\mathbf{direct}}=\text{'F'}$, x(j)${\mathbf{x}}\left(\mathit{j}\right)$ must contain xj${x}_{\mathit{j}}$, for j = 0,1,,n1$\mathit{j}=0,1,\dots ,n-1$;
• if direct = 'B'${\mathbf{direct}}=\text{'B'}$, x(2 × k)${\mathbf{x}}\left(2×\mathit{k}\right)$ and x(2 × k + 1)${\mathbf{x}}\left(2×\mathit{k}+1\right)$ must contain the real and imaginary parts respectively of zk${z}_{\mathit{k}}$, for k = 0,1,,n / 2$\mathit{k}=0,1,\dots ,n/2$. (Note that for the sequence zk${z}_{k}$ to be Hermitian, the imaginary part of z0${z}_{0}$, and of zn / 2${z}_{n/2}$ for n$n$ even, must be zero.)
3:     n – int64int32nag_int scalar
n$n$, the number of data values. The total number of prime factors of n, counting repetitions, must not exceed 30$30$.

None.

work

Output Parameters

1:     x( n + 2 ${\mathbf{n}}+2$) – double array
• if direct = 'F'${\mathbf{direct}}=\text{'F'}$ and x is declared with bounds (0 : n + 1)$\left(0:{\mathbf{n}}+1\right)$, x(2 × k)${\mathbf{x}}\left(2×\mathit{k}\right)$ and x(2 × k + 1)${\mathbf{x}}\left(2×\mathit{k}+1\right)$ will contain the real and imaginary parts respectively of k${\stackrel{^}{z}}_{\mathit{k}}$, for k = 0,1,,n / 2$\mathit{k}=0,1,\dots ,n/2$;
• if direct = 'B'${\mathbf{direct}}=\text{'B'}$ and x is declared with bounds (0 : n + 1)$\left(0:{\mathbf{n}}+1\right)$, x(j)${\mathbf{x}}\left(\mathit{j}\right)$ will contain j${\stackrel{^}{x}}_{\mathit{j}}$, for j = 0,1,,n1$\mathit{j}=0,1,\dots ,n-1$.
2:     ifail – int64int32nag_int scalar
${\mathrm{ifail}}={\mathbf{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${\mathbf{ifail}}=1$
 On entry, n < 1${\mathbf{n}}<1$.
ifail = 2${\mathbf{ifail}}=2$
 On entry, direct ≠ 'F'${\mathbf{direct}}\ne \text{'F'}$ or 'B'$\text{'B'}$.
ifail = 4${\mathbf{ifail}}=4$
 On entry, n has more than 30$30$ prime factors.
ifail = 5${\mathbf{ifail}}=5$
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×\mathrm{log}\left(n\right)$, but also depends on the factorization of n$n$. nag_sum_fft_realherm_1d (c06pa) is faster if the only prime factors of n$n$ are 2$2$, 3$3$ or 5$5$; and fastest of all if n$n$ is a power of 2$2$.

Example

```function nag_sum_fft_realherm_1d_example
direct = 'F';
x = [0.34907;
0.5489;
0.74776;
0.94459;
1.1385;
1.3285;
1.5137;
0;
0];
n = int64(7);
[xOut, ifail] = nag_sum_fft_realherm_1d(direct, x, n)
```
```

xOut =

2.4836
0
-0.2660
0.5309
-0.2577
0.2030
-0.2564
0.0581
0

ifail =

0

```
```function c06pa_example
direct = 'F';
x = [0.34907;
0.5489;
0.74776;
0.94459;
1.1385;
1.3285;
1.5137;
0;
0];
n = int64(7);
[xOut, ifail] = c06pa(direct, x, n)
```
```

xOut =

2.4836
0
-0.2660
0.5309
-0.2577
0.2030
-0.2564
0.0581
0

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