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 Parallelism and Performance

9 Further Comments

+− 10 Example

10.1 Program Text

10.2 Program Data

10.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.

Constraints:

$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 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_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.

10 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)

+− 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

NAG Library Function Document

nag_fft_complex (c06ecc)