c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_sum_fft_hermitian_2d (c06pwc)

## 1  Purpose

nag_sum_fft_hermitian_2d (c06pwc) computes the two-dimensional inverse discrete Fourier transform of a bivariate Hermitian sequence of complex data values.

## 2  Specification

 #include #include
 void nag_sum_fft_hermitian_2d (Integer m, Integer n, const Complex y[], double x[], NagError *fail)

## 3  Description

nag_sum_fft_hermitian_2d (c06pwc) computes the two-dimensional inverse discrete Fourier transform of a bivariate Hermitian sequence of complex data values ${z}_{{j}_{1}{j}_{2}}$, for ${j}_{1}=0,1,\dots ,m-1$ and ${j}_{2}=0,1,\dots ,n-1$.
The discrete Fourier transform is here defined by
 $x^ k1 k2 = 1mn ∑ j1=0 m-1 ∑ j2=0 n-1 z j1 j2 × exp 2πi j1 k1 m + j2 k2 n ,$
where ${k}_{1}=0,1,\dots ,m-1$ and ${k}_{2}=0,1,\dots ,n-1$. (Note the scale factor of $\frac{1}{\sqrt{mn}}$ in this definition.)
Because the input data satisfies conjugate symmetry (i.e., ${z}_{{k}_{1}{k}_{2}}$ is the complex conjugate of ${z}_{\left(m-{k}_{1}\right){k}_{2}}$, the transformed values ${\stackrel{^}{x}}_{{k}_{1}{k}_{2}}$ are real.
A call of nag_sum_fft_real_2d (c06pvc) followed by a call of nag_sum_fft_hermitian_2d (c06pwc) 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:     mIntegerInput
On entry: $m$, the first dimension of the transform.
Constraint: ${\mathbf{m}}\ge 1$.
2:     nIntegerInput
On entry: $n$, the second dimension of the transform.
Constraint: ${\mathbf{n}}\ge 1$.
3:     y[$\left({\mathbf{m}}/2+1\right)×{\mathbf{n}}$]const ComplexInput
On entry: the Hermitian sequence of complex input dataset $z$, where ${z}_{{j}_{1}{j}_{2}}$ is stored in ${\mathbf{y}}\left[{j}_{2}×\left(m/2+1\right)+{j}_{1}\right]$ , for ${j}_{1}=0,1,\dots ,m/2$ and ${j}_{2}=0,1,\dots ,n-1$.
4:     x[${\mathbf{m}}×{\mathbf{n}}$]doubleOutput
On exit: the real output dataset $\stackrel{^}{x}$, where ${\stackrel{^}{x}}_{{k}_{1}{k}_{2}}$ is stored in ${\mathbf{x}}\left[{k}_{2}×m+{k}_{1}\right]$, for ${k}_{1}=0,1,\dots ,m-1$ and ${k}_{2}=0,1,\dots ,n-1$.
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.
On entry, argument $⟨\mathit{\text{value}}⟩$ had an illegal value.
NE_INT
On entry, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{m}}\ge 1$.
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\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_2d (c06pvc) and a backward transform using nag_sum_fft_hermitian_2d (c06pwc), and comparing the results with the original sequence (in exact arithmetic they would be identical).

## 8  Parallelism and Performance

nag_sum_fft_hermitian_2d (c06pwc) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
nag_sum_fft_hermitian_2d (c06pwc) 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_hermitian_2d (c06pwc) is approximately proportional to $mn\mathrm{log}\left(mn\right)$, but also depends on the factors of $m$ and $n$. nag_sum_fft_hermitian_2d (c06pwc) is fastest if the only prime factors of $m$ and $n$ are $2$, $3$ and $5$, and is particularly slow if $m$ or $n$ is a large prime, or has large prime factors.
Workspace is internally allocated by nag_sum_fft_hermitian_2d (c06pwc). The total size of these arrays is approximately proportional to $mn$.