convolve {stats}R Documentation

Convolution of Sequences via FFT


Use the Fast Fourier Transform to compute the several kinds of convolutions of two sequences.


convolve(x, y, conj = TRUE, type = c("circular", "open", "filter"))


x, y

numeric sequences to be convolved, of the same length for type = "circular", the default. For type = "filter", y must not be longer than y (and typically is much shorter).


logical; if TRUE, take the complex conjugate before back-transforming (default, and used for usual convolution).


character; partially matched to "circular", "open", "filter". For "circular", the two sequences are treated as circular, i.e., periodic.

For "open" and "filter", the sequences are padded with 0s (from left and right) first; "filter" returns the middle sub-vector of "open", namely, the result of running a weighted mean of x with weights y.


The Fast Fourier Transform, fft, is used for efficiency.

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

Note that the usual definition of convolution of two sequences x and y is given by convolve(x, rev(y), type = "o").


If r <- convolve(x, y, type = "open") and n <- length(x), m <- length(y), then

r[k] = sum(i; x[k-m+i] * y[i])

where the sum is over all valid indices i, for k = 1, …, n+m-1.

If type == "circular", n = m is required, and the above is true for i , k = 1,…,n when x[j] := x[n+j] for j < 1.


Brillinger, D. R. (1981) Time Series: Data Analysis and Theory, Second Edition. San Francisco: Holden-Day.

See Also

fft, nextn, and particularly filter (from the stats package) which may be more appropriate.



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

(ctypes <- eval(formals(convolve)$type)[-1]) # all but "circular"
for(n in 1:500) {
 x <- rnorm(1+ rpois(1, 20))
 y <- rnorm(1+ rpois(1, sample(c(4,40), 1)))
 Lxy <- sapply(ctypes, function(T) convolve(x,y, type=T), simplify=FALSE)
 stopifnot(all.equal(Lxy$open,   Lxy$`1+open`,   tol=1e-14))
 stopifnot(all.equal(Lxy$filter, Lxy$`1+filter`, tol=1e-14))

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")

[Package stats version 3.4.0 Index]