# Fast Convolution

Michael Werman

Computer Science

The Hebrew University

Jerusalem 91904, Israel

werman@cs.huji.ac.il

Abstract:

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.