nag_fft_multiple_real (c06fpc) (PDF version)
c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_fft_multiple_real (c06fpc)

## 1  Purpose

nag_fft_multiple_real (c06fpc) computes the discrete Fourier transforms of $m$ sequences, each containing $n$ real data values.

## 2  Specification

 #include #include
 void nag_fft_multiple_real (Integer m, Integer n, double x[], const double trig[], NagError *fail)

## 3  Description

Given $m$ sequences of $n$ real data values ${x}_{\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 x 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 transformed values ${\stackrel{^}{z}}_{k}^{p}$ are complex, but for each value of $p$ the ${\stackrel{^}{z}}_{k}^{p}$ form a Hermitian sequence (i.e., ${\stackrel{^}{z}}_{n-k}^{p}$ is the complex conjugate of ${\stackrel{^}{z}}_{k}^{p}$), so they are completely determined by $mn$ real numbers. The first call of nag_fft_multiple_real (c06fpc) must be preceded by a call to nag_fft_init_trig (c06gzc) to initialize the array trig with trigonometric coefficients according to the value of n.
The discrete Fourier transform is sometimes defined using a positive sign in the exponential term
 $z ^ k p = 1 n ∑ j=0 n-1 x j p exp +2 π ijk / n .$
To compute this form, this function should be followed by a call to nag_multiple_conjugate_hermitian (c06gqc) to form the complex conjugates of 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 coding is provided for the factors 2, 3, 4, 5 and 6.
Brigham E O (1974) The Fast Fourier Transform Prentice–Hall
Temperton C (1983) Fast mixed-radix real Fourier transforms J. Comput. Phys. 52 340–350

## 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 real values in each sequence, $n$.
Constraint: ${\mathbf{n}}\ge 1$.
3:     x[${\mathbf{m}}×{\mathbf{n}}$]doubleInput/Output
On entry: the $m$ data sequences must be stored in x consecutively. If the data values 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 .$
On exit: the $m$ discrete Fourier transforms in Hermitian form, stored consecutively, overwriting the corresponding original sequences. If the $n$ components of the discrete Fourier transform ${\stackrel{^}{z}}_{k}^{p}$ are written as ${a}_{k}^{p}+{ib}_{k}^{p}$, then for $0\le k\le n/2$, ${a}_{k}^{p}$ is in array element ${\mathbf{x}}\left[\left(p-1\right)×n+k\right]$ and for $1\le k\le \left(n-1\right)/2$, ${b}_{k}^{p}$ is in array element ${\mathbf{x}}\left[\left(p-1\right)×n+n-k\right]$.
4:     trig[$2×{\mathbf{n}}$]const doubleInput
On entry: trigonometric coefficients as returned by a call of nag_fft_init_trig (c06gzc). nag_fft_multiple_real (c06fpc) makes a simple check to ensure that trig has been initialized and that the initialization is compatible with the value of n
5:     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).

Not applicable.

## 9  Further Comments

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 real data values and prints their discrete Fourier transforms (as computed by nag_fft_multiple_real (c06fpc)). The Fourier transforms are expanded into full complex form using nag_multiple_hermitian_to_complex (c06gsc) and printed. Inverse transforms are then calculated by calling nag_multiple_conjugate_hermitian (c06gqc) followed by nag_fft_multiple_hermitian (c06fqc) showing that the original sequences are restored.

### 10.1  Program Text

Program Text (c06fpce.c)

### 10.2  Program Data

Program Data (c06fpce.d)

### 10.3  Program Results

Program Results (c06fpce.r)

nag_fft_multiple_real (c06fpc) (PDF version)
c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual