c06pq:: 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_col (c06pq) 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_col (c06pq) is approximately proportional to

n m \log (n)

, but also depends on the factors of

n

. nag_sum_fft_realherm_1d_multi_col (c06pq) 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_col (c06pq) with

direct ='F'

), after expanding them from complex Hermitian form into a full complex sequences.

function c06pq_example


fprintf('c06pq 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];
x = transpose(x);
disp('Original data values:');
disp(x(1:n,:));

% Transform to get Hermitian sequences
direct = 'F';
[xt, ifail] = c06pq(direct, n, m, 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(1:n,j) = 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] = c06pq(direct, n, m, 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

c06pq example results

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

 Discrete Fourier transforms in complex Hermitian format:
             1          2          3
 1      1.0737     1.3961     1.1237
        0.0000     0.0000     0.0000

 2     -0.1041    -0.0365     0.0914
       -0.0044     0.4666    -0.0508

 3      0.1126     0.0780     0.3936
       -0.3738    -0.0607     0.3458

 4     -0.1467    -0.1521     0.1530
        0.0000     0.0000     0.0000
 
 Discrete Fourier transforms in full complex format:
             1          2          3
 1      1.0737     1.3961     1.1237
        0.0000     0.0000     0.0000

 2     -0.1041    -0.0365     0.0914
       -0.0044     0.4666    -0.0508

 3      0.1126     0.0780     0.3936
       -0.3738    -0.0607     0.3458

 4     -0.1467    -0.1521     0.1530
        0.0000     0.0000     0.0000

 5      0.1126     0.0780     0.3936
        0.3738     0.0607    -0.3458

 6     -0.1041    -0.0365     0.0914
        0.0044    -0.4666     0.0508
 
Original data as restored by inverse transform:
    0.3854    0.5417    0.9172
    0.6772    0.2983    0.0644
    0.1138    0.1181    0.6037
    0.6751    0.7255    0.6430
    0.6362    0.8638    0.0428
    0.1424    0.8723    0.4815

NAG Toolbox: nag_sum_fft_realherm_1d_multi_col (c06pq)

▸▿ Contents

Purpose

Syntax

Description