NAG Library Function Document

nag_fft_real (c06eac)

+− 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_real (c06eac) calculates the discrete Fourier transform of a sequence of

n

real data values.

2 Specification

#include <nag.h>

#include <nagc06.h>

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

3 Description

Given a sequence of

n

real data values

x_{j}

, for

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

, nag_fft_real (c06eac) calculates their discrete Fourier transform defined by

{\hat{z}}_{k} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} x_{j} \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{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.

The function nag_multiple_hermitian_to_complex (c06gsc) may be used to convert a Hermitian sequence to the corresponding complex sequence.

To compute the inverse discrete Fourier transform defined by

{\hat{w}}_{k} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} x_{j} \exp (+ i \frac{2 π j k}{n}),   for ​ k = 0, 1, \dots, n - 1,

this function should be followed by a call of nag_conjugate_hermitian (c06gbc) to form the complex conjugates of the

{\hat{z}}_{k}

nag_fft_real (c06eac) 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: n – IntegerInput: On entry: $n$ , the number of data values.
Constraint: $n > 1$ . 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.
2: x[n] – doubleInput/Output: On entry: $x [j]$ must contain $x_{j}$ , for $j = 0, 1, \dots, n - 1$ .

On exit: the discrete Fourier transform stored in Hermitian form. If the components of the transform ${\hat{z}}_{k}$ are written as $a_{k} + {i b}_{k}$ , then for $0 \leq k \leq n / 2$ , $a_{k}$ is contained in $x [k]$ , and for $1 \leq k \leq (n - 1) / 2$ , $b_{k}$ is contained in $x [n - k]$ . Elements of the sequence which are not explicitly stored are given by $a_{n - k} = a_{k}$ , $b_{n - k} = - b_{k}$ , $b_{o} = 0$ and, if $n$ is even, $b_{n / 2} = 0$ . (See also Section 10.)
3: fail – NagError *Input/Output: The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_C06_FACTOR_GT: At least one of the prime factors of n is greater than 19.
NE_C06_TOO_MANY_FACTORS: n has more than 20 prime factors.
NE_INT_ARG_LE: On entry, $n = ⟨value⟩$ .
Constraint: $n > 1$ .

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 \log (n)

, but also depends on the factorization of

n

. nag_fft_real (c06eac) is somewhat faster than average 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_real (c06eac) 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 and prints their discrete Fourier transform (as computed by nag_fft_real (c06eac)), after expanding it from Hermitian form into a full complex sequence. It then performs an inverse transform using nag_fft_hermitian (c06ebc) and nag_conjugate_hermitian (c06gbc), and prints the sequence so obtained alongside the original data values.

NAG Library Function Documentnag_fft_real (c06eac)