c06 Chapter Contents
NAG C Library Manual

# NAG Library Chapter Introductionc06 – Fourier Transforms

## 1  Scope of the Chapter

This chapter is concerned with the following tasks.
 (a) Calculating the discrete Fourier transform of a sequence of real or complex data values. (b) Calculating the discrete convolution or the discrete correlation of two sequences of real or complex data values using discrete Fourier transforms. (c) Direct summation of orthogonal series.

## 2  Background to the Problems

### 2.1  Discrete Fourier Transforms

#### 2.1.1  Complex transforms

Most of the functions in this chapter calculate the finite discrete Fourier transform (DFT) of a sequence of $n$ complex numbers ${z}_{\mathit{j}}$, for $\mathit{j}=0,1,\dots ,n-1$. The direct transform is defined by
 $z^k = 1n ∑ j=0 n-1 zj exp -i 2πjk n$ (1)
for $k=0,1,\dots ,n-1$. Note that equation (1) makes sense for all integral $k$ and with this extension ${\stackrel{^}{z}}_{k}$ is periodic with period $n$, i.e., ${\stackrel{^}{z}}_{k}={\stackrel{^}{z}}_{k±n}$, and in particular ${\stackrel{^}{z}}_{-k}={\stackrel{^}{z}}_{n-k}$. Note also that the scale-factor of $\frac{1}{\sqrt{n}}$ may be omitted in the definition of the DFT, and replaced by $\frac{1}{n}$ in the definition of the inverse.
If we write ${z}_{j}={x}_{j}+i{y}_{j}$ and ${\stackrel{^}{z}}_{k}={a}_{k}+i{b}_{k}$, then the definition of ${\stackrel{^}{z}}_{k}$ may be written in terms of sines and cosines as
 $ak = 1n ∑ j=0 n-1 xj cos 2πjk n + yj sin 2πjk n$
 $bk = 1n ∑ j= 0 n- 1 yj cos 2πjk n - xj sin 2πjk n .$
The original data values ${z}_{j}$ may conversely be recovered from the transform ${\stackrel{^}{z}}_{k}$ by an inverse discrete Fourier transform:
 $zj = 1n ∑ k=0 n-1 z^k exp +i 2πjk n$ (2)
for $j=0,1,\dots ,n-1$. If we take the complex conjugate of (2), we find that the sequence ${\stackrel{-}{z}}_{j}$ is the DFT of the sequence ${\stackrel{-}{\stackrel{^}{z}}}_{k}$. Hence the inverse DFT of the sequence ${\stackrel{^}{z}}_{k}$ may be obtained by taking the complex conjugates of the ${\stackrel{^}{z}}_{k}$; performing a DFT, and taking the complex conjugates of the result. (Note that the terms forward transform and backward transform are also used to mean the direct and inverse transforms respectively.)
The definition (1) of a one-dimensional transform can easily be extended to multidimensional transforms. For example, in two dimensions we have
 $z^ k1 k2 = 1 n1 n2 ∑ j1=0 n1-1 ∑ j2=0 n2-1 z j1 j2 exp -i 2 π j1 k1 n1 exp -i 2 π j2 k2 n2 .$
Note:  definitions of the discrete Fourier transform vary. Sometimes (2) is used as the definition of the DFT, and (1) as the definition of the inverse.

#### 2.1.2  Real transforms

If the original sequence is purely real valued, i.e., ${z}_{j}={x}_{j}$, then
 $z^k = ak + i bk = 1n ∑ j=0 n-1 xj exp -i 2πjk n$
and ${\stackrel{^}{z}}_{n-k}$ is the complex conjugate of ${\stackrel{^}{z}}_{k}$. Thus the DFT of a real sequence is a particular type of complex sequence, called a Hermitian sequence, or half-complex or conjugate symmetric, with the properties
 $a n-k = ak b n-k = -bk b0 = 0$
and, if $n$ is even, ${b}_{n/2}=0$.
Thus a Hermitian sequence of $n$ complex data values can be represented by only $n$, rather than $2n$, independent real values. This can obviously lead to economies in storage, with one scheme being used in this chapter. In this scheme, which will be referred to as the real storage format for Hermitian sequences, the real parts ${a}_{k}$ for $0\le k\le n/2$ are stored in normal order in the first $n/2+1$ locations of an array x of length $n$; the corresponding nonzero imaginary parts are stored in reverse order in the remaining locations of x. To clarify, if ${\mathbf{x}}\left[n\right]$ in your calling function, the following two tables illustrate the storage of the real and imaginary parts of ${\stackrel{^}{z}}_{k}$ for the two cases: $n$ even and $n$ odd.
If $n$ is even then the sequence has two purely real elements and is stored as follows:
 Index of x 0 1 2 $\dots$ $n/2$ $\dots$ $n-2$ $n-1$ Sequence ${a}_{0}$ ${a}_{1}+{ib}_{1}$ ${a}_{2}+{ib}_{2}$ $\dots$ ${a}_{n/2}$ $\dots$ ${a}_{2}-{ib}_{2}$ ${a}_{1}-{ib}_{1}$ Stored values ${a}_{0}$ ${a}_{1}$ ${a}_{2}$ $\dots$ ${a}_{n/2}$ $\dots$ ${b}_{2}$ ${b}_{1}$
 $x[k] = ak , for ​ k= 0, 1, …, n/2 , and x[n-k] = bk , for ​ k= 1, 2, …, n/2-1 .$
If $n$ is odd then the sequence has one purely real element and, letting $n=2s+1$, is stored as follows:
 Index of x 0 1 2 $\dots$ $s$ $s+1$ $\dots$ $n-2$ $n-1$ Sequence ${a}_{0}$ ${a}_{1}+{ib}_{1}$ ${a}_{2}+{ib}_{2}$ $\dots$ ${a}_{s}+i{b}_{s}$ ${a}_{s}-i{b}_{s}$ $\dots$ ${a}_{2}-{ib}_{2}$ ${a}_{1}-{ib}_{1}$ Stored values ${a}_{0}$ ${a}_{1}$ ${a}_{2}$ $\dots$ ${a}_{s}$ ${b}_{s}$ $\dots$ ${b}_{2}$ ${b}_{1}$
 $x[k] = ak , for ​ k= 0, 1, …, s , and x[n-k] = bk , for ​ k= 1, 2, …, s .$
Also, given a Hermitian sequence, the inverse (or backward) discrete transform produces a real sequence. That is,
 $xj = 1n a0 + 2 ∑ k=1 n/2-1 ak cos 2πjk n - bk sin 2πjk n + a n/2$
where ${a}_{n/2}=0$ if $n$ is odd.

#### 2.1.3  Real symmetric transforms

In many applications the sequence ${x}_{j}$ will not only be real, but may also possess additional symmetries which we may exploit to reduce further the computing time and storage requirements. For example, if the sequence ${x}_{j}$ is odd, $\left({x}_{j}={-x}_{n-j}\right)$, then the discrete Fourier transform of ${x}_{j}$ contains only sine terms. Rather than compute the transform of an odd sequence, we define the sine transform of a real sequence by
 $x^k = 2n ∑j=1 n-1 xj sin πjkn ,$
which could have been computed using the Fourier transform of a real odd sequence of length $2n$. In this case the ${x}_{j}$ are arbitrary, and the symmetry only becomes apparent when the sequence is extended. Similarly we define the cosine transform of a real sequence by
 $x^k = 2n 12 x0 + ∑ j=1 n-1 xj cos πjkn + 12 -1k xn$
which could have been computed using the Fourier transform of a real even sequence of length $2n$.
In addition to these ‘half-wave’ symmetries described above, sequences arise in practice with ‘quarter-wave’ symmetries. We define the quarter-wave sine transform by
 $x^k = 1n ∑ j=1 n-1 xj sin π j 2k-1 2n + 12 -1 k-1 xn$
which could have been computed using the Fourier transform of a real sequence of length $4n$ of the form
 $0,x1,…,xn,xn-1 ,…,x1,0,-x1,…,-xn, -x n-1 ,…, -x 1 .$
Similarly we may define the quarter-wave cosine transform by
 $x^k = 1n 12 x0 + ∑j= 1 n- 1 xj cos π j 2k- 1 2n$
which could have been computed using the Fourier transform of a real sequence of length $4n$ of the form
 $x0,x1,…, x n-1 ,0, -x n-1 ,…,-x0,-x1,…, -x n-1 ,0, x n-1 ,…,x1 .$

#### 2.1.4  Fourier integral transforms

The usual application of the discrete Fourier transform is that of obtaining an approximation of the Fourier integral transform
 $F s = ∫ -∞ ∞ f t exp -i 2 π s t dt$
when $f\left(t\right)$ is negligible outside some region $\left(0,c\right)$. Dividing the region into $n$ equal intervals we have
 $F s ≅ cn ∑ j=0 n-1 fj exp -i 2 π s j c n$
and so
 $Fk ≅ cn ∑ j= 0 n- 1 fj exp -i 2 π jk n$
for $k=0,1,\dots ,n-1$, where ${f}_{j}=f\left(jc/n\right)$ and ${F}_{k}=F\left(k/c\right)$.
Hence the discrete Fourier transform gives an approximation to the Fourier integral transform in the region $s=0$ to $s=n/c$.
If the function $f\left(t\right)$ is defined over some more general interval $\left(a,b\right)$, then the integral transform can still be approximated by the discrete transform provided a shift is applied to move the point $a$ to the origin.

#### 2.1.5  Convolutions and correlations

One of the most important applications of the discrete Fourier transform is to the computation of the discrete convolution or correlation of two vectors $x$ and $y$ defined (as in Brigham (1974)) by
• convolution: ${z}_{k}=\sum _{j=0}^{n-1}{x}_{j}{y}_{k-j}$
• correlation: ${w}_{k}=\sum _{j=0}^{n-1}{\stackrel{-}{x}}_{j}{y}_{k+j}$
(Here $x$ and $y$ are assumed to be periodic with period $n$.)
Under certain circumstances (see Brigham (1974)) these can be used as approximations to the convolution or correlation integrals defined by
 $z s = ∫ -∞ ∞ x t y s-t dt$
and
 $w s = ∫ -∞ ∞ x- t y s+t dt , -∞ < s < ∞ .$
For more general advice on the use of Fourier transforms, see Hamming (1962); more detailed information on the fast Fourier transform algorithm can be found in Gentleman and Sande (1966) and Brigham (1974).

#### 2.1.6  Applications to solving partial differential equations (PDEs)

A further application of the fast Fourier transform, and in particular of the Fourier transforms of symmetric sequences, is in the solution of elliptic PDEs. If an equation is discretized using finite differences, then it is possible to reduce the problem of solving the resulting large system of linear equations to that of solving a number of tridiagonal systems of linear equations. This is accomplished by uncoupling the equations using Fourier transforms, where the nature of the boundary conditions determines the choice of transforms – see Section 3.3. Full details of the Fourier method for the solution of PDEs may be found in Swarztrauber (1977) and Swarztrauber (1984).

### 2.2  Direct Summation of Orthogonal Series

For any series of functions ${\varphi }_{i}$ which satisfy a recurrence
 $ϕr+1 x + αr x ϕr x + βr x ϕr-1 x =0$
the sum
 $∑ r= 0 n ar ϕr x$
is given by
 $∑ r=0 n ar ϕr x = b0 x ϕ0 x + b1 x ϕ1 x + α0 x ϕ0 x$
where
 $br x + αr x br+ 1 x + βr+ 1 x br+ 2 x = ar b n+ 1 x = b n+ 2 x = 0 .$
This may be used to compute the sum of the series. For further reading, see Hamming (1962).

## 3  Recommendations on Choice and Use of Available Functions

### 3.1  One-dimensional Fourier Transforms

The choice of function is determined first of all by whether the data values constitute a real, Hermitian or general complex sequence. It is wasteful of time and storage to use an inappropriate function.
Two groups, each of three functions, are provided in real storage format.
 Group 1 Group 2 Real sequences nag_fft_real (c06eac) nag_fft_multiple_real (c06fpc) Hermitian sequences nag_fft_hermitian (c06ebc) nag_fft_multiple_hermitian (c06fqc) General complex sequences nag_fft_complex (c06ecc) nag_fft_multiple_complex (c06frc)
Group 1 functions each compute a single transform of length $n$, without requiring any extra working storage. The Group 1 functions impose some restrictions on the value of $n$, namely that no prime factor of $n$ may exceed $19$ and the total number of prime factors (including repetitions) may not exceed $20$ (though the latter restriction only becomes relevant when $n>{10}^{6}$).
Group 2 functions are all designed to perform several transforms in a single call, all with the same value of $n$. They are designed to be much faster than the Group 1 functions on vector-processing machines. They do however require more working storage. Even on scalar processors, they may be somewhat faster than repeated calls to Group 1 functions because of reduced overheads and because they pre-compute and store the required values of trigonometric functions. Group 2 functions impose no practical restrictions on the value of $n$; however, the fast Fourier transform algorithm ceases to be ‘fast’ if applied to values of $n$ which cannot be expressed as a product of small prime factors. All the above functions are particularly efficient if the only prime factors of $n$ are $2$, $3$ or $5$.
If extensive use is to be made of these functions and you are concerned about efficiency, you are advised to conduct your own timing tests.
To compute inverse (backward) discrete Fourier transforms the functions should be used in conjunction with the utility functions nag_conjugate_hermitian (c06gbc), nag_conjugate_complex (c06gcc) and nag_multiple_conjugate_hermitian (c06gqc) which form the complex conjugate of a Hermitian or general sequence of complex data values.

### 3.2  Half- and Quarter-wave Transforms

Four functions are provided for computing fast Fourier transforms (FFTs) of real symmetric sequences. nag_fft_multiple_sine (c06hac) computes compute multiple Fourier sine transforms, nag_fft_multiple_cosine (c06hbc) computes multiple Fourier cosine transforms, nag_fft_multiple_qtr_sine (c06hcc) computes multiple quarter-wave Fourier sine transforms, and nag_fft_multiple_qtr_cosine (c06hdc) computes multiple quarter-wave Fourier cosine transforms.

### 3.3  Application to Elliptic Partial Differential Equations

As described in Section 2.1, Fourier transforms may be used in the solution of elliptic PDEs.
nag_fft_multiple_sine (c06hac) may be used to solve equations where the solution is specified along the boundary.
nag_fft_multiple_cosine (c06hbc) may be used to solve equations where the derivative of the solution is specified along the boundary.
nag_fft_multiple_qtr_sine (c06hcc) may be used to solve equations where the solution is specified on the lower boundary, and the derivative of the solution is specified on the upper boundary.
nag_fft_multiple_qtr_cosine (c06hdc) may be used to solve equations where the derivative of the solution is specified on the lower boundary, and the solution is specified on the upper boundary.
For equations with periodic boundary conditions the full-range Fourier transforms computed by nag_fft_multiple_real (c06fpc) and nag_fft_multiple_hermitian (c06fqc) are appropriate.

### 3.4  Multidimensional Fourier Transforms

The following functions compute multidimensional discrete Fourier transforms of complex data:
 Real storage Complex storage 2 dimensions nag_fft_2d_complex (c06fuc) 3 dimensions nag_fft_3d (c06pxc) any number of dimensions nag_fft_multid_full (c06pjc)
The real storage format functions store sequences of complex data in two double arrays containing the real and imaginary parts of the sequence respectively. The complex storage format functions store the sequences in Complex arrays.
nag_fft_2d_complex (c06fuc) and nag_fft_3d (c06pxc) should be used in preference to nag_fft_multid_full (c06pjc) for two- and three-dimensional transforms, as they are easier to use and are likely to be more efficient, especially on vector processors.

### 3.5  Convolution and Correlation

nag_convolution_real (c06ekc) computes either the discrete convolution or the discrete correlation of two real vectors.

### 3.6  Direct Summation of Orthogonal Series

The only function available is nag_sum_cheby_series (c06dcc), which sums a finite Chebyshev series
 $∑ j=0 n cj Tj x , ∑ j=0 n cj T 2j x or ∑ j=0 n cj T 2j+1 x$
depending on the choice of an argument.

## 4  Functionality Index

 Complex conjugate,
 complex sequence nag_conjugate_complex (c06gcc)
 Hermitian sequence nag_conjugate_hermitian (c06gbc)
 multiple Hermitian sequences nag_multiple_conjugate_hermitian (c06gqc)
 Complex sequence from Hermitian sequences nag_multiple_hermitian_to_complex (c06gsc)
 Compute trigonometric functions nag_fft_init_trig (c06gzc)
 Convolution or Correlation,
 real vectors,
 space-saving nag_convolution_real (c06ekc)
 Discrete Fourier Transform,
 multidimensional,
 complex sequence,
 complex storage nag_fft_multid_full (c06pjc)
 multiple half- and quarter-wave transforms,
 Fourier cosine transforms nag_fft_multiple_cosine (c06hbc)
 Fourier sine transforms nag_fft_multiple_sine (c06hac)
 quarter-wave cosine transforms nag_fft_multiple_qtr_cosine (c06hdc)
 quarter-wave sine transforms nag_fft_multiple_qtr_sine (c06hcc)
 one-dimensional,
 multiple transforms,
 complex sequence,
 real storage by rows nag_fft_multiple_complex (c06frc)
 Hermitian sequence,
 real storage by rows nag_fft_multiple_hermitian (c06fqc)
 real sequence,
 real storage by rows nag_fft_multiple_real (c06fpc)
 multi-variable,
 complex sequence,
 complex storage nag_fft_multid_single (c06pfc)
 single transforms,
 complex sequence,
 space-saving,
 real storage nag_fft_complex (c06ecc)
 Hermitian sequence,
 space-saving,
 real storage nag_fft_hermitian (c06ebc)
 real sequence,
 space-saving,
 real storage nag_fft_real (c06eac)
 three-dimensional,
 complex sequence,
 complex storage nag_fft_3d (c06pxc)
 two-dimensional,
 complex sequence,
 real storage nag_fft_2d_complex (c06fuc)
 Summation of Chebyshev series nag_sum_cheby_series (c06dcc)

None.

## 6  References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall
Davies S B and Martin B (1979) Numerical inversion of the Laplace transform: A survey and comparison of methods J. Comput. Phys. 33 1–32
Fox L and Parker I B (1968) Chebyshev Polynomials in Numerical Analysis Oxford University Press
Gentleman W S and Sande G (1966) Fast Fourier transforms for fun and profit Proc. Joint Computer Conference, AFIPS 29 563–578
Hamming R W (1962) Numerical Methods for Scientists and Engineers McGraw–Hill
Shanks D (1955) Nonlinear transformations of divergent and slowly convergent sequences J. Math. Phys. 34 1–42
Swarztrauber P N (1977) The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson's equation on a rectangle SIAM Rev. 19(3) 490–501
Swarztrauber P N (1984) Fast Poisson solvers Studies in Numerical Analysis (ed G H Golub) Mathematical Association of America
Swarztrauber P N (1986) Symmetric FFT's Math. Comput. 47(175) 323–346
Wynn P (1956) On a device for computing the ${e}_{m}\left({\mathrm{S}}_{n}\right)$ transformation Math. Tables Aids Comput. 10 91–96

c06 Chapter Contents