NAG Library Function Document

nag_convolution_real (c06ekc)

if $operation = Nag_Convolution$ , the discrete convolution of $x$ and $y$ , defined by
$z_{k} = \sum_{j = 0}^{n - 1} x_{j} y_{k - j} = \sum_{j = 0}^{n - 1} x_{k - j} y_{j};$
if $operation = Nag_Correlation$ , the discrete correlation of $x$ and $y$ defined by
$w_{k} = \sum_{j = 0}^{n - 1} x_{j} y_{k + j} .$

Here

x

and

y

are real vectors, assumed to be periodic, with period

n

, i.e.,

x_{j} = x_{j \pm n} = x_{j \pm 2 n} = \dots

;

z

and

w

are then also periodic with period

n

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.

\hat{x}

\hat{y}

\hat{z}

and

\hat{w}

are the discrete Fourier transforms of these sequences, i.e.,

{\hat{x}}_{k} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} x_{j} \exp (- i \frac{2 π j k}{n}), etc.,

then

{\hat{z}}_{k} = \sqrt{n} {\hat{x}}_{k} {\hat{y}}_{k}

and

{\hat{w}}_{k} = \sqrt{n} {\bar{\hat{x}}}_{k} {\hat{y}}_{k}

(the bar denoting complex conjugate).

This function calls the same auxiliary functions as nag_fft_real (c06eac) and nag_fft_hermitian (c06ebc) to compute discrete Fourier transforms, and there are some restrictions on the value of

n

4 References

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

5 Arguments

1: $operation$ – Nag_VectorOpInput

On entry: the computation to be performed.

$operation = Nag_Convolution$: $z_{k} = \sum_{j = 0}^{n - 1} x_{j} y_{k - j}$ .
$operation = Nag_Correlation$: $w_{k} = \sum_{j = 0}^{n - 1} x_{j} y_{k + j}$ .

Constraint:

operation = Nag_Convolution

Nag_Correlation

2: $n$ – IntegerInput

On entry:

n

, the number of values, in one period of the vectors x and y.

Constraints:

$n > 1$ ;
The largest prime factor of n must not exceed 19, and the total number of prime factors of n, counting repetitions, must not exceed 20.

3: $x [n]$ – doubleInput/Output

On entry: the elements of one period of the vector

x

x [j]

must contain

x_{j}

, for

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

On exit: the corresponding elements of the discrete convolution or correlation.

4: $y [n]$ – doubleInput/Output

On entry: the elements of one period of the vector

y

y [j]

must contain

y_{j}

, for

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

On exit: the discrete Fourier transform of the convolution or correlation returned in the array x; the transform is stored in Hermitian form, exactly as described in the document nag_fft_real (c06eac).

5: $fail$ – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_BAD_PARAM: On entry, argument operation had an illegal value.
NE_C06_FACTOR_GT: At least one of the prime factors of n is greater than 19.
NE_C06_TOO_MANY_FACTORS: n has more than 20 prime factors.
NE_INT_ARG_LE: On entry, $n = 〈value〉$ .
Constraint: $n > 1$ .

7 Accuracy

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

8 Parallelism and Performance

Not applicable.

9 Further Comments

The time taken is approximately proportional to

n \log (n)

, but also depends on the factorization of

n

. nag_convolution_real (c06ekc) is somewhat faster than average if the only prime factors of

n

are

2

3

5

; and fastest of all if

n

is a power of

2

On the other hand, nag_convolution_real (c06ekc) is particularly slow if

n

has several unpaired prime factors, i.e., if the ‘square-free’ part of

n

has several factors.

10 Example

This example reads in the elements of one period of two real vectors

x

and

y

and prints their discrete convolution and correlation (as computed by nag_convolution_real (c06ekc)). In realistic computations the number of data values would be much larger.

NAG Library Function Documentnag_convolution_real (c06ekc)

▸▿ Contents

1 Purpose

2 Specification

3 Description