naginterfaces.library.sum.fft_​realherm_​1d

naginterfaces.library.sum.fft_realherm_1d(direct, x)

fft_realherm_1d calculates the discrete Fourier transform of a sequence of $n$ real data values or of a Hermitian sequence of $n$ complex data values stored in compact form in a float array.

For full information please refer to the NAG Library document for c06pa

https://support.nag.com/numeric/nl/nagdoc_30.2/flhtml/c06/c06paf.html

Parameters

directstr, length 1

If the forward transform as defined in Notes is to be computed, $direct$ must be set equal to ‘F’.

If the backward transform is to be computed, $direct$ must be set equal to ‘B’.

xfloat, array-like, shape $(n+2)$

If $x$ is declared with bounds $(0:n+1)$ in the function from which fft_realherm_1d is called:

if $direct=\text{'F'}$, $x\left[\text{j}\right]$ must contain $x_{\text{j}}$, for $\text{j}=0,1,\dots ,n-1$;

if $direct=\text{'B'}$, $x[2\times \text{k}]$ and $x[2\times \text{k}+1]$ must contain the real and imaginary parts respectively of $z_{\text{k}}$, for $\text{k}=0,1,\dots ,n/2$. (Note that for the sequence $z_k$ to be Hermitian, the imaginary part of $z_0$, and of $z_{n/2}$ for $n$ even, must be zero.)

Returns

xfloat, ndarray, shape $(n+2)$

If $direct=\text{'F'}$ and $x$ is declared with bounds $(0:n+1)$, $x[2\times \text{k}]$ and $x[2\times \text{k}+1]$ will contain the real and imaginary parts respectively of ${\hat{z}}_{\text{k}}$, for $\text{k}=0,1,\dots ,n/2$;

if $direct=\text{'B'}$ and $x$ is declared with bounds $(0:n+1)$, $x\left[\text{j}\right]$ will contain ${\hat{x}}_{\text{j}}$, for $\text{j}=0,1,\dots ,n-1$.

Raises

NagValueError

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $2$)

On entry, $direct=⟨value⟩$.

Constraint: $direct=\text{'F'}$ or $\text{'B'}$.

(errno $3$)

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.

Notes

Given a sequence of $n$ real data values $x_{\text{j}}$, for $\text{j}=0,1,\dots ,n-1$, fft_realherm_1d calculates their discrete Fourier transform (in the forward direction) defined by

$${\hat{z}}_k=\frac{1}{\sqrt{n}}\sum _{j=0}^{n-1}{x}_j\times exp\left(-i\frac{2\pi jk}{n}\right)\text{,}k=0,1,\dots ,n-1\text{.}$$

The transformed values ${\hat{z}}_k$ are complex, but they form a Hermitian sequence (i.e., ${\hat{z}}_{n-k}$ is the complex conjugate of ${\hat{z}}_k$), so they are completely determined by $n$ real numbers (since ${\hat{z}}_0$ is real, as is ${\hat{z}}_{n/2}$ for $n$ even).

Alternatively, given a Hermitian sequence of $n$ complex data values $z_j$, this function calculates their inverse (backward) discrete Fourier transform defined by

$${\hat{x}}_k=\frac{1}{\sqrt{n}}\sum _{j=0}^{n-1}{z}_j\times exp\left(i\frac{2\pi jk}{n}\right)\text{,}k=0,1,\dots ,n-1\text{.}$$

The transformed values ${\hat{x}}_k$ are real.

(Note the scale factor of $\frac{1}{\sqrt{n}}$ in the above definitions.)

A call of fft_realherm_1d with $direct=\text{'F'}$ followed by a call with $direct=\text{'B'}$ will restore the original data.

fft_realherm_1d 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: fft_real_2d() and fft_hermitian_2d() on setting $\text{n}=1$. This pair use a different storage solution; real data is stored in a float 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