nag_fft_2d_complex (c06fuc) (PDF version)
c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_fft_2d_complex (c06fuc)

 Contents

    1  Purpose
    7  Accuracy

1  Purpose

nag_fft_2d_complex (c06fuc) computes the two-dimensional discrete Fourier transform of a bivariate sequence of complex data values.

2  Specification

#include <nag.h>
#include <nagc06.h>
void  nag_fft_2d_complex (Integer m, Integer n, double x[], double y[], const double trigm[], const double trign[], NagError *fail)

3  Description

nag_fft_2d_complex (c06fuc) computes the two-dimensional discrete Fourier transform of a bivariate sequence of complex data values z j 1 j 2 , where j 1 = 0 , 1 , , m - 1 , j 2 = 0 , 1 , , n - 1 .
The discrete Fourier transform is here defined by
z ^ k 1 k 2 = 1 mn j 1 = 0 m-1 j 2 = 0 n-1 z j 1 j 2 exp -2 π i j 1 k 1 m + j 2 k 2 n  
for k 1 = 0 , 1 , , m - 1 ; k 2 = 0 , 1 , , n - 1 .
(Note the scale factor of 1 / mn  in this definition.)
The first call of nag_fft_2d_complex (c06fuc) must be preceded by calls to nag_fft_init_trig (c06gzc) to initialize the trigm and trign arrays with trigonometric coefficients according to the value of m and n respectively.
To compute the inverse discrete Fourier transform, defined with exp +2 π i  in the above formula instead of exp -2 π i , this function should be preceded and followed by calls of nag_conjugate_complex (c06gcc) to form the complex conjugates of the data values and the transform.
This function calls nag_fft_multiple_complex (c06frc) to perform multiple one-dimensional discrete Fourier transforms by the fast Fourier transform algorithm in Brigham (1974).

4  References

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:     m IntegerInput
On entry: the number of rows, m , of the bivariate data sequence.
Constraint: m1 .
2:     n IntegerInput
On entry: the number of columns, n , of the bivariate data sequence.
Constraint: n1 .
3:     x[m×n] doubleInput/Output
4:     y[m×n] doubleInput/Output
On entry: the real and imaginary parts of the complex data values must be stored in arrays x and y respectively. Each row of the data must be stored consecutively; hence if the real parts of z j 1 , j 2  are denoted by x j 1 , j 2 , for j 1 = 0 , 1 , , m - 1 , j 2 = 0 , 1 , , n - 1 , then the mn  elements of x must contain the values
x 0,0 , x 0,1 , , x 0 , n - 1 , x 1,0 , x 1,1 , , x 1 , n - 1 , , x m - 1 , 0 , x m - 1 , 1 , , x m - 1 , n - 1 .  
The imaginary parts must be ordered similarly in y.
On exit: the real and imaginary parts respectively of the corresponding elements of the computed transform.
5:     trigm[2×m] const doubleInput
6:     trign[2×n] const doubleInput
On entry: trigm and trign must contain trigonometric coefficients as returned by calls of nag_fft_init_trig (c06gzc). nag_fft_2d_complex (c06fuc) performs a simple check to ensure that both arrays have been initialized and that they are compatible with m and n. If m=n  the same array may be supplied for trigm and trign.
7:     fail NagError *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 m and trigm array are incompatible or trigm array not initialized.
Value of n and trign array are incompatible or trign array not initialized.
NE_INT_ARG_LT
On entry, m=value.
Constraint: m1.
On entry, n=value.
Constraint: n1.

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.

9  Further Comments

The time taken is approximately proportional to mn log mn , but also depends on the factorization of the individual dimensions m  and n . The function is somewhat faster than average if their only prime factors are 2, 3 or 5; and fastest of all if they are powers of 2; it is particularly slow if m  or n  is a large prime, or has large prime factors.

10  Example

This program reads in a bivariate sequence of complex data values and prints the two-dimensional Fourier transform. It then performs an inverse transform and prints the sequence so obtained, which may be compared to the original data values.

10.1  Program Text

Program Text (c06fuce.c)

10.2  Program Data

Program Data (c06fuce.d)

10.3  Program Results

Program Results (c06fuce.r)


nag_fft_2d_complex (c06fuc) (PDF version)
c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2015