\Header{convolve}{Fast Convolution}
\keyword{math}{convolve}
\keyword{dplot}{convolve}
\begin{Description}\relax
Use the Fast Fourier Transform to compute the several kinds of
convolutions of two sequences.\end{Description}
\begin{Usage}
\begin{verbatim}
convolve(x, y, conj = TRUE, type = c("circular", "open", "filter"))
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{x,y}] numeric sequences \emph{of the same length} to be
convolved.
\item[\code{conj}] logical; if \code{TRUE}, take the complex \emph{conjugate}
before back-transforming (default, and used for usual convolution).
\item[\code{type}] character; one of \code{"circular"}, \code{"open"},
\code{"filter"} (beginning of word is ok).  For \code{circular}, the
two sequences are treated as \emph{circular}, i.e., periodic.

For \code{open} and \code{filter}, the sequences are padded with
\code{0}s (from left and right) first; \code{"filter"} returns the
middle sub-vector of \code{"open"}, namely, the result of running a
weighted mean of \code{x} with weights \code{y}.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
The Fast Fourier Transform, \code{\Link{fft}}, is used for efficiency.

The input sequences \code{x} and  \code{y} must have the same length if
\code{circular} is true.

Note that the usual definition of convolution of two sequences
\code{x} and \code{y} is given by \code{convolve(x, rev(y), type = "o")}.\end{Details}
\begin{Value}
If \code{r <- convolve(x,y, type = "open")}
and \code{n <- length(x)}, \code{m <- length(y)}, then
\deqn{r_k = \sum_{i} x_{k-m+i} y_{i}}{r[k] = sum(i; x[k-m+i] * y[i])}
where the sum is over all valid indices \eqn{i}{}, for \eqn{k = 1,\dots, n+m-1}{}

If \code{type == "circular"}, \eqn{n = m}{} is required, and the above is
true for \eqn{i , k = 1,\dots,n}{} when
\eqn{x_{j} := x_{n+j}}{x[j] := x[n+j]} for \eqn{j < 1}{}.\end{Value}
\begin{References}\relax
Brillinger, D. R. (1981)
\emph{Time Series: Data Analysis and Theory}, Second Edition.
San Francisco: Holden-Day.\end{References}
\begin{SeeAlso}\relax
\code{\Link{fft}}, \code{\Link{nextn}}, and particularly
\code{\Link{filter}} (from the \pkg{ts} package) which may be
more appropriate.\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
x <- c(0,0,0,100,0,0,0)
y <- c(0,0,1, 2 ,1,0,0)/4
zapsmall(convolve(x,y))         #  *NOT* what you first thought.
zapsmall(convolve(x, y[3:5], type="f")) # rather
x <- rnorm(50)
y <- rnorm(50)
# Circular convolution *has* this symmetry:
all.equal(convolve(x,y, conj = FALSE),
          rev(convolve(rev(y),x)))

n <- length(x <- -20:24)
y <- (x-10)^2/1000 + rnorm(x)/8

Han <- function(y) # Hanning
       convolve(y, c(1,2,1)/4, type = "filter")

plot(x,y, main="Using  convolve(.) for Hanning filters")
lines(x[-c(1  , n)      ], Han(y), col="red")
lines(x[-c(1:2, (n-1):n)], Han(Han(y)), lwd=2, col="dark blue")
\end{ExampleCode}
\end{Examples}

