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 (c06fk)

Purpose

nag_sum_convcorr_real (c06fk) calculates the circular convolution or correlation of two real vectors of period nn (using a work array for extra speed).

Syntax

[x, y, ifail] = c06fk(job, x, y, 'n', n)
[x, y, ifail] = nag_sum_convcorr_real(job, x, y, 'n', n)

Description

nag_sum_convcorr_real (c06fk) 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_realherm_1d (c06pa) to compute discrete Fourier transforms.

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 (c06fk) 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 (c06fk) 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

work

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 zkzk are written as ak + ibkak+ibk, then for 0kn / 20kn/2, akak is contained in y(k)yk, and for 1kn1 / 21kn-1/2, bkbk is contained in y(nk)yn-k. (See also 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 (c06fk) 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.

Example

function nag_sum_convcorr_real_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(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 c06fk_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] = c06fk(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