c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_sum_fft_real_3d (c06pyc)

## 1  Purpose

nag_sum_fft_real_3d (c06pyc) computes the three-dimensional discrete Fourier transform of a trivariate sequence of real data values.

## 2  Specification

 #include #include
 void nag_sum_fft_real_3d (Integer n1, Integer n2, Integer n3, const double x[], Complex y[], NagError *fail)

## 3  Description

nag_sum_fft_real_3d (c06pyc) computes the three-dimensional discrete Fourier transform of a trivariate sequence of real data values ${x}_{{j}_{1}{j}_{2}{j}_{3}}$, for ${j}_{1}=0,1,\dots ,{n}_{1}-1$, ${j}_{2}=0,1,\dots ,{n}_{2}-1$ and ${j}_{3}=0,1,\dots ,{n}_{3}-1$.
The discrete Fourier transform is here defined by
 $z^ k1 k2 k3 = 1 n1 n2 n3 ∑ j1=0 n1-1 ∑ j2=0 n2-1 ∑ j3=0 n3-1 x j1 j2 j3 × exp -2πi j1 k1 n1 + j2 k2 n2 + j3 k3 n3 ,$
where ${k}_{1}=0,1,\dots ,{n}_{1}-1$, ${k}_{2}=0,1,\dots ,{n}_{2}-1$ and ${k}_{3}=0,1,\dots ,{n}_{3}-1$. (Note the scale factor of $\frac{1}{\sqrt{{n}_{1}{n}_{2}{n}_{3}}}$ in this definition.)
The transformed values ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}{k}_{3}}$ are complex. Because of conjugate symmetry (i.e., ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}{k}_{3}}$ is the complex conjugate of ${\stackrel{^}{z}}_{\left({n}_{1}-{k}_{1}\right){k}_{2}{k}_{3}}$), only slightly more than half of the Fourier coefficients need to be stored in the output.
A call of nag_sum_fft_real_3d (c06pyc) followed by a call of nag_sum_fft_hermitian_3d (c06pzc) will restore the original data.
This function performs multiple one-dimensional discrete Fourier transforms by the fast Fourier transform (FFT) algorithm in Brigham (1974) and Temperton (1983).

## 4  References

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:     n1IntegerInput
On entry: ${n}_{1}$, the first dimension of the transform.
Constraint: ${\mathbf{n1}}\ge 1$.
2:     n2IntegerInput
On entry: ${n}_{2}$, the second dimension of the transform.
Constraint: ${\mathbf{n2}}\ge 1$.
3:     n3IntegerInput
On entry: ${n}_{3}$, the third dimension of the transform.
Constraint: ${\mathbf{n3}}\ge 1$.
4:     x[${\mathbf{n1}}×{\mathbf{n2}}×{\mathbf{n3}}$]const doubleInput
On entry: the real input dataset $x$, where ${x}_{{j}_{1}{j}_{2}{j}_{3}}$ is stored in ${\mathbf{x}}\left[{j}_{3}×{n}_{1}{n}_{2}+{j}_{2}×{n}_{1}+{j}_{1}\right]$, for ${j}_{1}=0,1,\dots ,{n}_{1}-1$, ${j}_{2}=0,1,\dots ,{n}_{2}-1$ and ${j}_{3}=0,1,\dots ,{n}_{3}-1$.
5:     y[$\mathit{dim}$]ComplexOutput
Note: the dimension, dim, of the array y must be at least $\left({\mathbf{n1}}/2+1\right)×{\mathbf{n2}}×{\mathbf{n3}}$.
On exit: the complex output dataset $\stackrel{^}{z}$, where ${\stackrel{^}{z}}_{{k}_{1}{k}_{2}{k}_{3}}$ is stored in ${\mathbf{y}}\left[{k}_{3}×\left({n}_{1}/2+1\right){n}_{2}+{k}_{2}×\left({n}_{1}/2+1\right)+{k}_{1}\right]$, for ${k}_{1}=0,1,\dots ,{n}_{1}/2$, ${k}_{2}=0,1,\dots ,{n}_{2}-1$ and ${k}_{3}=0,1,\dots ,{n}_{3}-1$. Note the first dimension is cut roughly by half to remove the redundant information due to conjugate symmetry.
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.
On entry, argument $⟨\mathit{\text{value}}⟩$ had an illegal value.
NE_INT
On entry, ${\mathbf{n1}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n1}}\ge 1$.
On entry, ${\mathbf{n2}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n2}}\ge 1$.
On entry, ${\mathbf{n3}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n3}}\ge 1$.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.

## 7  Accuracy

Some indication of accuracy can be obtained by performing a forward transform using nag_sum_fft_real_3d (c06pyc) and a backward transform using nag_sum_fft_hermitian_3d (c06pzc), and comparing the results with the original sequence (in exact arithmetic they would be identical).

## 8  Parallelism and Performance

nag_sum_fft_real_3d (c06pyc) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
nag_sum_fft_real_3d (c06pyc) makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.

The time taken by nag_sum_fft_real_3d (c06pyc) is approximately proportional to ${n}_{1}{n}_{2}{n}_{3}\mathrm{log}\left({n}_{1}{n}_{2}{n}_{3}\right)$, but also depends on the factors of ${n}_{1}$, ${n}_{2}$ and ${n}_{3}$. nag_sum_fft_real_3d (c06pyc) is fastest if the only prime factors of ${n}_{1}$, ${n}_{2}$ and ${n}_{3}$ are $2$, $3$ and $5$, and is particularly slow if one of the dimensions is a large prime, or has large prime factors.
Workspace is internally allocated by nag_sum_fft_real_3d (c06pyc). The total size of these arrays is approximately proportional to ${n}_{1}{n}_{2}{n}_{3}$.

## 10  Example

This example reads in a trivariate sequence of real data values and prints their discrete Fourier transforms as computed by nag_sum_fft_real_3d (c06pyc). Inverse transforms are then calculated by calling nag_sum_fft_hermitian_3d (c06pzc) showing that the original sequences are restored.

### 10.1  Program Text

Program Text (c06pyce.c)

### 10.2  Program Data

Program Data (c06pyce.d)

### 10.3  Program Results

Program Results (c06pyce.r)