c06 Chapter Contents
c06 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_convolution_real (c06ekc)

## 1  Purpose

nag_convolution_real (c06ekc) calculates the circular convolution or correlation of two real vectors of period $n$.

## 2  Specification

 #include #include
 void nag_convolution_real (Nag_VectorOp operation, Integer n, double x[], double y[], NagError *fail)

## 3  Description

nag_convolution_real (c06ekc) computes:
• if ${\mathbf{operation}}=\mathrm{Nag_Convolution}$, the discrete convolution of $x$ and $y$, defined by
 $zk = ∑ j=0 n-1 xj yk-j = ∑ j=0 n-1 xk-j yj ;$
• if ${\mathbf{operation}}=\mathrm{Nag_Correlation}$, the discrete correlation of $x$ and $y$ defined by
 $wk = ∑ j=0 n-1 xj yk+j .$
Here $x$ and $y$ are real vectors, assumed to be periodic, with period $n$, i.e., ${x}_{j}={x}_{j±n}={x}_{j±2n}=\dots \text{}$; $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.
If $\stackrel{^}{x}$, $\stackrel{^}{y}$, $\stackrel{^}{z}$ and $\stackrel{^}{w}$ are the discrete Fourier transforms of these sequences, i.e.,
 $x^k = 1n ∑ j=0 n-1 xj exp -i 2πjk n , etc.,$
then ${\stackrel{^}{z}}_{k}=\sqrt{n}{\stackrel{^}{x}}_{k}{\stackrel{^}{y}}_{k}$ and ${\stackrel{^}{w}}_{k}=\sqrt{n}{\stackrel{-}{\stackrel{^}{x}}}_{k}{\stackrel{^}{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:     operationNag_VectorOpInput
On entry: the computation to be performed.
${\mathbf{operation}}=\mathrm{Nag_Convolution}$
${z}_{k}={\sum }_{j=0}^{n-1}{x}_{j}{y}_{k-j}$.
${\mathbf{operation}}=\mathrm{Nag_Correlation}$
${w}_{k}={\sum }_{j=0}^{n-1}{x}_{j}{y}_{k+j}$.
Constraint: ${\mathbf{operation}}=\mathrm{Nag_Convolution}$ or $\mathrm{Nag_Correlation}$.
2:     nIntegerInput
On entry: $n$, the number of values, in one period of the vectors x and y.
Constraints:
• ${\mathbf{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$. ${\mathbf{x}}\left[\mathit{j}\right]$ must contain ${x}_{\mathit{j}}$, for $\mathit{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$. ${\mathbf{y}}\left[\mathit{j}\right]$ must contain ${y}_{\mathit{j}}$, for $\mathit{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:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

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, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}>1$.

## 7  Accuracy

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

## 8  Parallelism and Performance

Not applicable.

The time taken is approximately proportional to $n\mathrm{log}\left(n\right)$, 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$ or $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.

### 10.1  Program Text

Program Text (c06ekce.c)

### 10.2  Program Data

Program Data (c06ekce.d)

### 10.3  Program Results

Program Results (c06ekce.r)