Suppose $\{f_n\}$ and $\{g_n\}$ are finite sequences of complex numbers with $0\leq n \leq N-1$. The convolution $\{h_n\}$ of these two sequences is $$ h_n = \sum_{m = 0}^{N-1} f_m\; g_{n - m}\, . $$ It is well-known that this convolution can be computed rapidly using a fast Fourier transform (FFT): $$ h = {FFT}^{-1}\bigl\{FFT\{f\}\; FFT\{g\} \bigr\}\, . $$
Suppose, however, that I have a slightly altered problem. Let $\phi(x)$ be a function of a real variable $x$, which is as smooth as we need it to be, and define the sequence $\{h_n\}$ by $$ h_n = \sum_{m = 0}^{N-1} f_m\; \phi\left(\frac{n}{\alpha} - m\right)\, , $$ where $\alpha$ is a real number $>0$, and $0\leq n \leq N-1$. This is almost, but not quite, a convolution. If we had $\alpha = 1$, we could use the FFT method above to evaluate this efficiently. What about the case where $\alpha \neq 1$? Is there a way to transform this into a case that can be handled by a FFT? Or is there some other way of evaluating this quickly for large $N$? Is there something obvious I'm missing?
Thanks very much for any and all help.
Edited to note that the index $n$ in the equation above runs from $0$ to $N-1$.
If we let $p=n/\alpha$, then what you have written is
$$ h\left( p \right) = \sum_{m=0}^{N-1}{f(m) \cdot \phi \left( p - m\right) }, $$
which is a normal convolution. What you want is $h(p)$ evaluated at $p=n/\alpha$, $n=0,1,2,\dots$. If we take a simple example and let $\alpha = 1/2$ so that $p=2n$, then the signal you want is $h(p)$, $p=0,2,4,6,\dots$, which implies that you can just discard every other output sample. Of course, if you are just going to discard every other output sample, why bother calculating it in the first place?
There are efficient ways to implement this combination of filtering and sample rate change for rational $\alpha$ (polyphase filters are one example that comes to mind), but it is very implementation specific and, moreover, will depend on the value of $\alpha$. Hence, I'd refer you to a signal processing text until you have a more specific question/problem.