c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_fft_multiple_complex (c06frc)

## 1  Purpose

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

## 2  Specification

 #include #include
 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}_{\mathit{j}}^{\mathit{p}}$, for $\mathit{j}=0,1,\dots ,n-1$ and $\mathit{p}=1,2,\dots ,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/\sqrt{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 ${\stackrel{^}{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.
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: ${\mathbf{m}}\ge 1$.
2:     nIntegerInput
On entry: the number of complex values in each sequence, $n$.
Constraint: ${\mathbf{n}}\ge 1$.
3:     x[${\mathbf{m}}×{\mathbf{n}}$]doubleInput/Output
4:     y[${\mathbf{m}}×{\mathbf{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}_{\mathit{j}}^{p}$, for $\mathit{j}=0,1,\dots ,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×{\mathbf{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, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{m}}\ge 1$.
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 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.

The time taken is approximately proportional to $nm\mathrm{log}\left(n\right)$, 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)