c06pp:: Summation of Series (NAG Toolbox)

Given

m

sequences of

n

real data values

x_{j}^{p}

, for

j = 0, 1, \dots, n - 1

and

p = 1, 2, \dots, m

, nag_sum_fft_realherm_1d_multi_row (c06pp) simultaneously calculates the Fourier transforms of all the sequences defined by

{\hat{z}}_{k}^{p} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} x_{j}^{p} \times \exp (- i \frac{2 π j k}{n}), k = 0, 1, \dots, n - 1 ​ and ​ p = 1, 2, \dots, m .

The transformed values

{\hat{z}}_{k}^{p}

are complex, but for each value of

p

the

{\hat{z}}_{k}^{p}

form a Hermitian sequence (i.e.,

{\hat{z}}_{n - k}^{p}

is the complex conjugate of

{\hat{z}}_{k}^{p}

), so they are completely determined by

m n

real numbers (since

{\hat{z}}_{0}^{p}

is real, as is

{\hat{z}}_{n / 2}^{p}

for

n

even).

Alternatively, given

m

Hermitian sequences of

n

complex data values

z_{j}^{p}

, this function simultaneously calculates their inverse (backward) discrete Fourier transforms defined by

{\hat{x}}_{k}^{p} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} z_{j}^{p} \times \exp (i \frac{2 π j k}{n}), k = 0, 1, \dots, n - 1 ​ and ​ p = 1, 2, \dots, m .

The transformed values

{\hat{x}}_{k}^{p}

are real.

The function uses a variant of the fast Fourier transform (FFT) algorithm (see Brigham (1974)) known as the Stockham self-sorting algorithm, which is described in Temperton (1983). Special coding is provided for the factors

2

3

4

and

5

References

Parameters

Compulsory Input Parameters

Optional Input Parameters

Output Parameters

Error Indicators and Warnings

Accuracy

Further Comments

The time taken by nag_sum_fft_realherm_1d_multi_row (c06pp) is approximately proportional to

n m \log (n)

, but also depends on the factors of

n

. nag_sum_fft_realherm_1d_multi_row (c06pp) is fastest if the only prime factors of

n

are

2

3

and

5

, and is particularly slow if

n

is a large prime, or has large prime factors.

Example

This example reads in sequences of real data values and prints their discrete Fourier transforms (as computed by nag_sum_fft_realherm_1d_multi_row (c06pp) with

direct ='F'

), after expanding them from complex Hermitian form into a full complex sequences. Inverse transforms are then calculated by calling nag_sum_fft_realherm_1d_multi_row (c06pp) with

direct ='B'

showing that the original sequences are restored.

function c06pp_example


fprintf('c06pp example results\n\n');

% 3 real sequences stored as rows
m = int64(3);
n = int64(6);
x = [0.3854   0.6772   0.1138   0.6751   0.6362  0.1424  0  0;
     0.5417   0.2983   0.1181   0.7255   0.8638  0.8723  0  0;
     0.9172   0.0644   0.6037   0.6430   0.0428  0.4815  0  0];
disp('Original data values:');
disp(x(:,1:n));

% Transform to get Hermitian sequences
direct = 'F';
[xt, ifail] = c06pp(direct, m, n, x);
zt = xt(:,1:2:n+1) + i*xt(:,2:2:n+2);
title = 'Discrete Fourier transforms in complex Hermitian format:';
[ifail] = x04da('General','Non-unit', zt, title);

for j = 1:m
  zt(j,1:n) = nag_herm2complex(n,xt(j,:));
end
title = 'Discrete Fourier transforms in full complex format:';
disp(' ');
[ifail] = x04da('General','Non-unit', zt, title);

% Restore data by back transform
direct = 'B';
[xr, ifail] = c06pp(direct, m, n, xt);
disp(' ');
disp('Original data as restored by inverse transform:');
disp(xr(:,1:n));



function [z] = nag_herm2complex(n,x);
  z(1) = complex(x(1));
  for j = 2:floor(double(n)/2) + 1
    z(j) = x(2*j-1) + i*x(2*j);
    z(n-j+2) = x(2*j-1) - i*x(2*j);
  end

c06pp example results

Original data values:
    0.3854    0.6772    0.1138    0.6751    0.6362    0.1424
    0.5417    0.2983    0.1181    0.7255    0.8638    0.8723
    0.9172    0.0644    0.6037    0.6430    0.0428    0.4815

 Discrete Fourier transforms in complex Hermitian format:
             1          2          3          4
 1      1.0737    -0.1041     0.1126    -0.1467
        0.0000    -0.0044    -0.3738     0.0000

 2      1.3961    -0.0365     0.0780    -0.1521
        0.0000     0.4666    -0.0607     0.0000

 3      1.1237     0.0914     0.3936     0.1530
        0.0000    -0.0508     0.3458     0.0000
 
 Discrete Fourier transforms in full complex format:
             1          2          3          4          5          6
 1      1.0737    -0.1041     0.1126    -0.1467     0.1126    -0.1041
        0.0000    -0.0044    -0.3738     0.0000     0.3738     0.0044

 2      1.3961    -0.0365     0.0780    -0.1521     0.0780    -0.0365
        0.0000     0.4666    -0.0607     0.0000     0.0607    -0.4666

 3      1.1237     0.0914     0.3936     0.1530     0.3936     0.0914
        0.0000    -0.0508     0.3458     0.0000    -0.3458     0.0508
 
Original data as restored by inverse transform:
    0.3854    0.6772    0.1138    0.6751    0.6362    0.1424
    0.5417    0.2983    0.1181    0.7255    0.8638    0.8723
    0.9172    0.0644    0.6037    0.6430    0.0428    0.4815

NAG Toolbox: nag_sum_fft_realherm_1d_multi_row (c06pp)

▸▿ Contents

Purpose

Syntax

Description