NAG Library Function Document

nag_fft_complex (c06ecc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

nag_fft_complex (c06ecc) calculates the discrete Fourier transform of a sequence of

n

complex data values.

2 Specification

#include <nag.h>

#include <nagc06.h>

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

3 Description

Given a sequence of

n

complex data values

z_{j}

, for

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

, nag_fft_complex (c06ecc) calculates their discrete Fourier transform defined by

{\hat{z}}_{k} = a_{k} + {i b}_{k} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} z_{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.)

To compute the inverse discrete Fourier transform defined by

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

this function should be preceded and followed by calls of nag_conjugate_complex (c06gcc) to form the complex conjugates of the

z_{j}

and the

{\hat{z}}_{k}

nag_fft_complex (c06ecc) 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}$ , the real part of $z_{j}$ , for $j = 0, 1, \dots, n - 1$ .

On exit: the real parts $a_{k}$ of the components of the discrete Fourier transform. $a_{k}$ is contained in $x [k]$ , for $k = 0, 1, \dots, n - 1$ .
3: y[n] – doubleInput/Output: On entry: $y [j]$ must contain $y_{j}$ , the imaginary part of $z_{j}$ , for $j = 0, 1, \dots, n - 1$ .

On exit: the imaginary parts $b_{k}$ of the components of the discrete Fourier transform. $b_{k}$ is contained in $y [k]$ , for $k = 0, 1, \dots, n - 1$ .
4: 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 Further Comments

The time taken is approximately proportional to

n \log n

, but also depends on the factorization of

n

. nag_fft_complex (c06ecc) 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_complex (c06ecc) is particularly slow if

n

has several unpaired prime factors, i.e., if the ‘square-free’ part of

n

has several factors.

9 Example

This example reads in a sequence of complex data values and prints their discrete Fourier transform. It then performs an inverse transform using nag_fft_complex (c06ecc) and nag_conjugate_complex (c06gcc), and prints the sequence so obtained alongside the original data values.

NAG Library Function Documentnag_fft_complex (c06ecc)