NAG Library Function Document

nag_fft_hermitian (c06ebc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

+− 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

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 <nag.h>

#include <nagc06.h>

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

3 Description

Given a Hermitian sequence of

n

complex data values

z_{j}

(i.e., a sequence such that

z_{0}

is real and

z_{n - j}

is the complex conjugate of

z_{j}

, for

j = 1, 2, \dots, n - 1

), nag_fft_hermitian (c06ebc) calculates their discrete Fourier transform defined by

{\hat{x}}_{k} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} z_{j} \times \exp (- i \frac{2 π j k}{n}), k = 0, 1, \dots, n - 1 .

(Note the scale factor of

\frac{1}{\sqrt{n}}

in this definition.) The transformed values

{\hat{x}}_{k}

are purely real (see also the c06 Chapter Introduction).

To compute the inverse discrete Fourier transform defined by

{\hat{y}}_{k} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} z_{j} \times \exp (+ i \frac{2 π j k}{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 $(0 : n - 1)$ in the function from which nag_fft_hermitian (c06ebc) is called, then for $0 \leq j \leq n / 2$ , $x_{j}$ is contained in $x [j - 1]$ , and for $1 \leq j \leq (n - 1) / 2$ , $y_{j}$ is contained in $x [n - j]$ . (See also Section 2.1.2 in the c06 Chapter Introduction and Section 10.)

On exit: the components of the discrete Fourier transform ${\hat{x}}_{k}$ . If x is declared with bounds $(0 : n - 1)$ in the function from which nag_fft_hermitian (c06ebc) is called, then ${\hat{x}}_{k}$ is stored in $x [k]$ , for $k = 0, 1, \dots, n - 1$ .
2: n – IntegerInput: 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: $n > 1$ .
3: fail – NagError *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 $⟨value⟩$ had an illegal value.
NE_INT: On entry, $n = ⟨value⟩$ .
Constraint: $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$ . $n = ⟨value⟩$ .
NE_TOO_MANY_FACTORS: n has more than $20$ prime factors. $n = ⟨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).

8 Parallelism and Performance

Not applicable.

9 Further Comments

The time taken is approximately proportional to

n \times \log (n)

, but also depends on the factorization of

n

. nag_fft_hermitian (c06ebc) is faster if the only prime factors of

n

are

2

3

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.

NAG Library Function Documentnag_fft_hermitian (c06ebc)