nag_fft_multiple_complex (c06frc) (PDF version)
c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_fft_multiple_complex (c06frc)

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

nag_fft_multiple_complex (c06frc) computes the discrete Fourier transforms of m  sequences, each containing n  complex data values.

2  Specification

#include <nag.h>
#include <nagc06.h>
void  nag_fft_multiple_complex (Integer m, Integer n, double x[], double y[], const double trig[], NagError *fail)

3  Description

Given m  sequences of n  complex data values z j p , for j=0,1,,n - 1 and p=1,2,,m, this function simultaneously calculates the Fourier transforms of all the sequences defined by
z ^ k p = 1 n j=0 n-1 z j p exp -2 π ijk / n ,   for ​ k = 0 , 1 , , n - 1 ; p = 1 , 2 , , m .
(Note the scale factor 1 / n  in this definition.)
The first call of nag_fft_multiple_complex (c06frc) must be preceded by a call to nag_fft_init_trig (c06gzc) to initialize the array trig with trigonometric coefficients.
The discrete Fourier transform is sometimes defined using a positive sign in the exponential term
z ^ k p = 1 n j=0 n-1 z j p exp +2 π ijk / n .
To compute this form, this function should be preceded and followed by a call of nag_conjugate_complex (c06gcc) to form the complex conjugates of the z j p  and the z ^ k p .
The function uses a variant of the Fast Fourier Transform algorithm (Brigham (1974)) known as the Stockham self-sorting algorithm, which is described in Temperton (1983). Special code is provided for the factors 2, 3, 4, 5 and 6.

4  References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall
Temperton C (1983) Self-sorting mixed-radix fast Fourier transforms J. Comput. Phys. 52 1–23

5  Arguments

1:     mIntegerInput
On entry: the number of sequences to be transformed, m .
Constraint: m1 .
2:     nIntegerInput
On entry: the number of complex values in each sequence, n .
Constraint: n1 .
3:     x[m×n]doubleInput/Output
4:     y[m×n]doubleInput/Output
On entry: the real and imaginary parts of the complex data must be stored in x and y respectively. Each of the m  sequences must be stored consecutively; hence if the real parts of the p th sequence to be transformed are denoted by x j p , for j=0,1,, n - 1, then the mn  elements of the array x must contain the values
x 0 1 , x 1 1 , , x n-1 1 , x 0 2 , x 1 2 , , x n-1 2 , , x 0 m , x 1 m , , x n-1 m .
The imaginary parts must be ordered similarly in y.
On exit: x and y are overwritten by the real and imaginary parts of the complex transforms.
5:     trig[2×n]const doubleInput
On entry: trigonometric coefficients as returned by a call of nag_fft_init_trig (c06gzc). nag_fft_multiple_complex (c06frc) makes a simple check to ensure that trig has been initialized and that the initialization is compatible with the value of n.
6:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

6  Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
NE_C06_NOT_TRIG
Value of n and trig array are incompatible or trig array not initialized.
NE_INT_ARG_LT
On entry, m=value.
Constraint: m1.
On entry, n=value.
Constraint: n1.

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 nm logn , but also depends on the factors of n . The function is fastest if the only prime factors of n  are 2, 3 and 5, and is particularly slow if n  is a large prime, or has large prime factors.

10  Example

This program reads in sequences of complex data values and prints their discrete Fourier transforms (as computed by nag_fft_multiple_complex (c06frc)). Inverse transforms are then calculated using nag_conjugate_complex (c06gcc) and nag_fft_multiple_complex (c06frc) and printed out, showing that the original sequences are restored.

10.1  Program Text

Program Text (c06frce.c)

10.2  Program Data

Program Data (c06frce.d)

10.3  Program Results

Program Results (c06frce.r)


nag_fft_multiple_complex (c06frc) (PDF version)
c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2014