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.