Fast Convolution



Michael Werman


Computer Science

The Hebrew University

Jerusalem 91904, Israel




We present a very simple and fast algorithm to compute the convolution

of an arbitrary sequence $x$ with a sequence of a specific type, $a$.

The sequence $a$ is any linear combination of polynomials, exponentials

and trigonometric terms. The number of steps for computing the convolution

depends on a certain {\it complexity} of $a$ and not on its length, thus

making it feasible to convolve a sequence with very large kernels fast.