convJU: Fast Sequences Convolution

In martakarass/convo: Fast Computation of Running Sample Statistics

Description

Computes convolutions of two sequences via Fast Fourier Transform

Usage

convJU(x, y)

Arguments

x	numeric sequence
y	numeric sequence, of equal or shorter length than x sequence

Details

Use the Fast Fourier Transform to compute convolutions of two sequences. If sequences are of different length, the shorter one get a suffix of 0's. Following convention of stats::convolve function, if r <- convolve(x, y, type = "open") and n <- length(x), m <- length(y), then

r[k] = ∑_i x[k-m+i] \cdot y[i])

where the sum is over all valid indices i.

FFT formulation is useful for implementing an efficient numerical convolution: the standard convolution algorithm has quadratic computational complexity. From convolution theorem, the complexity of the convolution can be reduced from O(n^{2}) to O(n\log n) with fast Fourier transform.

Value

numeric sequence

Examples

## Not run: 
x <- sin(seq(0, 1, length.out = 1000) * 2 * pi * 6)
y <- rep(1, 100)
convJU(x, y)

## End(Not run)

martakarass/convo documentation built on May 16, 2019, 11:08 a.m.