nag_fft_hermitian (c06ebc) (PDF version)
c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_fft_hermitian (c06ebc)

## 1  Purpose

nag_fft_hermitian (c06ebc) calculates the discrete Fourier transform of a Hermitian sequence of $n$ complex data values. (No extra workspace required.)

## 2  Specification

 #include #include
 void nag_fft_hermitian (double x[], Integer n, NagError *fail)

## 3  Description

Given a Hermitian sequence of $n$ complex data values ${z}_{\mathit{j}}$ (i.e., a sequence such that ${z}_{0}$ is real and ${z}_{n-\mathit{j}}$ is the complex conjugate of ${z}_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n-1$), nag_fft_hermitian (c06ebc) calculates their discrete Fourier transform defined by
 $x^k = 1n ∑ j=0 n-1 zj × exp -i 2πjk n , k= 0, 1, …, n-1 .$
(Note the scale factor of $\frac{1}{\sqrt{n}}$ in this definition.) The transformed values ${\stackrel{^}{x}}_{k}$ are purely real (see also the c06 Chapter Introduction).
To compute the inverse discrete Fourier transform defined by
 $y^k = 1n ∑ j=0 n-1 zj × exp +i 2πjk n ,$
this function should be preceded by a call of nag_conjugate_hermitian (c06gbc) to form the complex conjugates of the ${z}_{j}$.
nag_fft_hermitian (c06ebc) uses the fast Fourier transform (FFT) algorithm (see Brigham (1974)). There are some restrictions on the value of $n$ (see Section 5).

## 4  References

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

## 5  Arguments

1:     x[n]doubleInput/Output
On entry: the sequence to be transformed stored in Hermitian form. If the data values ${z}_{j}$ are written as ${x}_{j}+i{y}_{j}$, and if x is declared with bounds $\left(0:{\mathbf{n}}-1\right)$ in the function from which nag_fft_hermitian (c06ebc) is called, then for $0\le j\le n/2$, ${x}_{j}$ is contained in ${\mathbf{x}}\left[j-1\right]$, and for $1\le j\le \left(n-1\right)/2$, ${y}_{j}$ is contained in ${\mathbf{x}}\left[n-j\right]$. (See also Section 2.1.2 in the c06 Chapter Introduction and Section 10.)
On exit: the components of the discrete Fourier transform ${\stackrel{^}{x}}_{k}$. If x is declared with bounds $\left(0:{\mathbf{n}}-1\right)$ in the function from which nag_fft_hermitian (c06ebc) is called, then ${\stackrel{^}{x}}_{\mathit{k}}$ is stored in ${\mathbf{x}}\left[\mathit{k}\right]$, for $\mathit{k}=0,1,\dots ,n-1$.
2:     nIntegerInput
On entry: $n$, the number of data values. The largest prime factor of n must not exceed $19$, and the total number of prime factors of n, counting repetitions, must not exceed $20$.
Constraint: ${\mathbf{n}}>1$.
3:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

NE_BAD_PARAM
On entry, argument $⟨\mathit{\text{value}}⟩$ had an illegal value.
NE_INT
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}>1$.
NE_INTERNAL_ERROR
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.
NE_PRIME_FACTOR
At least one of the prime factors of n is greater than $19$. ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
NE_TOO_MANY_FACTORS
n has more than $20$ prime factors. ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.

## 7  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).

Not applicable.

## 9  Further Comments

The time taken is approximately proportional to $n×\mathrm{log}\left(n\right)$, but also depends on the factorization of $n$. nag_fft_hermitian (c06ebc) is faster if the only prime factors of $n$ are $2$, $3$ or $5$; and fastest of all if $n$ is a power of $2$.
On the other hand, nag_fft_hermitian (c06ebc) is particularly slow if $n$ has several unpaired prime factors, i.e., if the ‘square-free’ part of $n$ has several factors.

## 10  Example

This example reads in a sequence of real data values which is assumed to be a Hermitian sequence of complex data values stored in Hermitian form. The input sequence is expanded into a full complex sequence and printed alongside the original sequence. The discrete Fourier transform (as computed by nag_fft_hermitian (c06ebc)) is printed out. It then performs an inverse transform using nag_fft_real (c06eac) and nag_conjugate_hermitian (c06gbc), and prints the sequence so obtained alongside the original data values.

### 10.1  Program Text

Program Text (c06ebce.c)

### 10.2  Program Data

Program Data (c06ebce.d)

### 10.3  Program Results

Program Results (c06ebce.r)

nag_fft_hermitian (c06ebc) (PDF version)
c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual