hide long namesshow long names
hide short namesshow short names
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_convcorr_real_nowork (c06ek)

Purpose

nag_sum_convcorr_real_nowork (c06ek) calculates the circular convolution or correlation of two real vectors of period nn. (No extra workspace is required.)
Note: this function is scheduled to be withdrawn, please see c06ek in Advice on Replacement Calls for Withdrawn/Superseded Routines..

Syntax

[x, y, ifail] = c06ek(job, x, y, 'n', n)
[x, y, ifail] = nag_sum_convcorr_real_nowork(job, x, y, 'n', n)

Description

nag_sum_convcorr_real_nowork (c06ek) computes:
Here xx and yy are real vectors, assumed to be periodic, with period nn, i.e., xj = xj ± n = xj ± 2n = xj = x j±n = x j±2n = ; zz and ww are then also periodic with period nn.
Note:  this usage of the terms ‘convolution’ and ‘correlation’ is taken from Brigham (1974). The term ‘convolution’ is sometimes used to denote both these computations.
If x^ , y^ , z^  and w^  are the discrete Fourier transforms of these sequences, i.e.,
n1
k = 1/(sqrt(n))xj × exp(i(2πjk)/n), etc.,
j = 0
x^k = 1n j=0 n-1 xj × exp( -i 2πjk n ) , etc.,
then k = sqrt(n) . k k z^k = n . x^k y^k  and k = sqrt(n) . k k w^k = n . x^- k y^k  (the bar denoting complex conjugate).
This function calls the same auxiliary functions as nag_sum_fft_real_1d_nowork (c06ea) and nag_sum_fft_hermitian_1d_nowork (c06eb) to compute discrete Fourier transforms, and there are some restrictions on the value of nn.

References

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

Parameters

Compulsory Input Parameters

1:     job – int64int32nag_int scalar
The computation to be performed.
job = 1job=1
zk = j = 0n1 xj ykj zk = j=0 n-1 x j y k-j  (convolution);
job = 2job=2
wk = j = 0n1 xj yk + j w k = j=0 n-1 x j y k+j  (correlation).
Constraint: job = 1job=1 or 22.
2:     x(n) – double array
n, the dimension of the array, must satisfy the constraint n > 1n>1.
The elements of one period of the vector xx. If x is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_convcorr_real_nowork (c06ek) is called, then x(j) xj  must contain xjxj, for j = 0,1,,n1j=0,1,,n-1.
3:     y(n) – double array
n, the dimension of the array, must satisfy the constraint n > 1n>1.
The elements of one period of the vector yy. If y is declared with bounds (0 : n1)(0:n-1) in the function from which nag_sum_convcorr_real_nowork (c06ek) is called, then y(j)yj must contain yjyj, for j = 0,1,,n1j=0,1,,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.)
nn, the number of values in one period of the vectors x and y.
Constraint: n > 1n>1.

Input Parameters Omitted from the MATLAB Interface

None.

Output Parameters

1:     x(n) – double array
The corresponding elements of the discrete convolution or correlation.
2:     y(n) – double array
The discrete Fourier transform of the convolution or correlation returned in the array x; the transform is stored in Hermitian form. If the components of the transform are:
Ẑk = ak + i bk Ẑn − k = ak − i bk }
  k = 0,1, … n / 2
Z^k = ak + i bk Z^ n-k = ak - i bk } k=0,1,n/2
where b0b0 and bn / 2bn/2 when nn is even then x(k + 1)xk+1 holds akak and x(nk + 1)xn-k+1 holds nonzero bkbk (see Section [Real transforms] in the C06 Chapter Introduction).
3:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
At least one of the prime factors of n is greater than 1919.
  ifail = 2ifail=2
n has more than 2020 prime factors.
  ifail = 3ifail=3
On entry,n1n1.
  ifail = 4ifail=4
On entry,job1job1 or 22.

Accuracy

The results should be accurate to within a small multiple of the machine precision.

Further Comments

The time taken is approximately proportional to n × log(n)n × log(n), but also depends on the factorization of nn. nag_sum_convcorr_real_nowork (c06ek) is faster if the only prime factors of nn are 22, 33 or 55; and fastest of all if nn is a power of 22.
On the other hand, nag_sum_convcorr_real_nowork (c06ek) is particularly slow if nn has several unpaired prime factors, i.e., if the ‘square-free’ part of nn has several factors. For such values of nn, nag_sum_convcorr_real (c06fk) (which requires additional double workspace) is considerably faster.

Example

function nag_sum_convcorr_real_nowork_example
job = int64(1);
x = [1;
     1;
     1;
     1;
     1;
     0;
     0;
     0;
     0];
y = [0.5;
     0.5;
     0.5;
     0.5;
     0;
     0;
     0;
     0;
     0];
[xOut, yOut, ifail] = nag_sum_convcorr_real_nowork(job, x, y)
 

xOut =

    0.5000
    1.0000
    1.5000
    2.0000
    2.0000
    1.5000
    1.0000
    0.5000
    0.0000


yOut =

    3.3333
   -1.0585
   -0.0082
    0.0833
    0.0667
   -0.0243
   -0.1443
   -0.0465
   -0.8882


ifail =

                    0


function c06ek_example
job = int64(1);
x = [1;
     1;
     1;
     1;
     1;
     0;
     0;
     0;
     0];
y = [0.5;
     0.5;
     0.5;
     0.5;
     0;
     0;
     0;
     0;
     0];
[xOut, yOut, ifail] = c06ek(job, x, y)
 

xOut =

    0.5000
    1.0000
    1.5000
    2.0000
    2.0000
    1.5000
    1.0000
    0.5000
    0.0000


yOut =

    3.3333
   -1.0585
   -0.0082
    0.0833
    0.0667
   -0.0243
   -0.1443
   -0.0465
   -0.8882


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