Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_sum_fft_complex_1d_sep (c06fc)

## Purpose

nag_sum_fft_complex_1d_sep (c06fc) calculates the discrete Fourier transform of a sequence of n$n$ complex data values (using a work array for extra speed).

## Syntax

[x, y, ifail] = c06fc(x, y, 'n', n)
[x, y, ifail] = nag_sum_fft_complex_1d_sep(x, y, 'n', n)

## Description

Given a sequence of n$n$ complex data values zj ${z}_{\mathit{j}}$, for j = 0,1,,n1$\mathit{j}=0,1,\dots ,n-1$, nag_sum_fft_complex_1d_sep (c06fc) calculates their discrete Fourier transform defined by
 n − 1 ẑk = ak + ibk = 1/(sqrt(n)) ∑ zj × exp( − i(2πjk)/n),  k = 0,1, … ,n − 1. j = 0
$z^k = ak + i bk = 1n ∑ j=0 n-1 zj × exp( -i 2πjk n ) , k= 0, 1, …, n-1 .$
(Note the scale factor of 1/(sqrt(n)) $\frac{1}{\sqrt{n}}$ in this definition.)
To compute the inverse discrete Fourier transform defined by
 n − 1 ŵk = 1/(sqrt(n)) ∑ zj × exp( + i(2πjk)/n), j = 0
$w^k = 1n ∑ j=0 n-1 zj × exp( +i 2πjk n ) ,$
this function should be preceded and followed by the complex conjugation of the data values and the transform (by negating the imaginary parts stored in y$y$).
nag_sum_fft_complex_1d_sep (c06fc) uses the fast Fourier transform (FFT) algorithm (see Brigham (1974)). There are some restrictions on the value of n$n$ (see Section [Parameters]).

## References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall

## Parameters

### Compulsory Input Parameters

1:     x(n) – double array
n, the dimension of the array, must satisfy the constraint n > 1${\mathbf{n}}>1$.
If x is declared with bounds (0 : n1)$\left(0:{\mathbf{n}}-1\right)$ in the function from which nag_sum_fft_complex_1d_sep (c06fc) is called, then x(j)${\mathbf{x}}\left(\mathit{j}\right)$ must contain xj${x}_{\mathit{j}}$, the real part of zj${z}_{\mathit{j}}$, for j = 0,1,,n1$\mathit{j}=0,1,\dots ,n-1$.
2:     y(n) – double array
n, the dimension of the array, must satisfy the constraint n > 1${\mathbf{n}}>1$.
If y is declared with bounds (0 : n1)$\left(0:{\mathbf{n}}-1\right)$ in the function from which nag_sum_fft_complex_1d_sep (c06fc) is called, then y(j)${\mathbf{y}}\left(\mathit{j}\right)$ must contain yj${y}_{\mathit{j}}$, the imaginary part of zj${z}_{\mathit{j}}$, for j = 0,1,,n1$\mathit{j}=0,1,\dots ,n-1$.

### Optional Input Parameters

1:     n – int64int32nag_int scalar
Default: The dimension of the arrays x, y. (An error is raised if these dimensions are not equal.)
n$n$, the number of data values. The largest prime factor of n must not exceed 19$19$, and the total number of prime factors of n, counting repetitions, must not exceed 20$20$.
Constraint: n > 1${\mathbf{n}}>1$.

work

### Output Parameters

1:     x(n) – double array
The real parts ak${a}_{k}$ of the components of the discrete Fourier transform. If x is declared with bounds (0 : n1)$\left(0:{\mathbf{n}}-1\right)$ in the function from which nag_sum_fft_complex_1d_sep (c06fc) is called, then for 0 k n1$0\le k\le n-1$, ak${a}_{k}$ is contained in x(k)${\mathbf{x}}\left(k\right)$.
2:     y(n) – double array
The imaginary parts bk${b}_{k}$ of the components of the discrete Fourier transform. If y is declared with bounds (0 : n1)$\left(0:{\mathbf{n}}-1\right)$ in the function from which nag_sum_fft_complex_1d_sep (c06fc) is called, then for 0kn1$0\le k\le n-1$, bk${b}_{k}$ is contained in y(k)${\mathbf{y}}\left(k\right)$.
3:     ifail – int64int32nag_int scalar
${\mathrm{ifail}}={\mathbf{0}}$ unless the function detects an error (see [Error Indicators and Warnings]).

## Error Indicators and Warnings

Errors or warnings detected by the function:
ifail = 1${\mathbf{ifail}}=1$
At least one of the prime factors of n is greater than 19$19$.
ifail = 2${\mathbf{ifail}}=2$
n has more than 20$20$ prime factors.
ifail = 3${\mathbf{ifail}}=3$
 On entry, n ≤ 1${\mathbf{n}}\le 1$.
ifail = 4${\mathbf{ifail}}=4$
An unexpected error has occurred in an internal call. Check all function calls and array dimensions. Seek expert help.

## 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).

The time taken is approximately proportional to n × log(n)$n×\mathrm{log}\left(n\right)$, but also depends on the factorization of n$n$. nag_sum_fft_complex_1d_sep (c06fc) is faster if the only prime factors of n$n$ are 2$2$, 3$3$ or 5$5$; and fastest of all if n$n$ is a power of 2$2$.

## Example

```function nag_sum_fft_complex_1d_sep_example
x = [0.34907;
0.5489;
0.74776;
0.94459;
1.1385;
1.3285;
1.5137];
y = [-0.37168;
-0.35669;
-0.31175;
-0.23702;
-0.13274;
0.00074;
0.16298];
[xOut, yOut, ifail] = nag_sum_fft_complex_1d_sep(x, y)
```
```

xOut =

2.4836
-0.5518
-0.3671
-0.2877
-0.2251
-0.1483
0.0198

yOut =

-0.4710
0.4968
0.0976
-0.0586
-0.1748
-0.3084
-0.5650

ifail =

0

```
```function c06fc_example
x = [0.34907;
0.5489;
0.74776;
0.94459;
1.1385;
1.3285;
1.5137];
y = [-0.37168;
-0.35669;
-0.31175;
-0.23702;
-0.13274;
0.00074;
0.16298];
[xOut, yOut, ifail] = c06fc(x, y)
```
```

xOut =

2.4836
-0.5518
-0.3671
-0.2877
-0.2251
-0.1483
0.0198

yOut =

-0.4710
0.4968
0.0976
-0.0586
-0.1748
-0.3084
-0.5650

ifail =

0

```

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013