<p>Suppose I have $n+1$-dimensional vectors $a$ and $b$. For each $i = 0, \dots, n$, I also have integers $0 \leq j_0(i) \leq j_1(i) \leq i$. I want to compute the following variant of a convolution:</p>

<p>$$
c_i = \sum_{j_0(i) \leq j \leq j_1(i)} a_j b_{i-j}
$$</p>

<p>If $j_0(i) = 0, j_1(i) = i$ for all $i$ this is a standard convolution, so you can do this via FFT in time $O(n \log n)$. </p>

<p>Are there any good algorithms for this when $j_0, j_1$ are arbitrary?</p>

CC BY-SA 3.0
2012-08-16T02:46:11.487Z
You're out by one I think. Both $a_0$ and $a_n$ are potentially referenced which means $a$ must have n+1 elements.
Andrew Tomazos
CC BY-SA 3.0
2012-08-16T13:12:17.097Z
@user10310 you're right, I fixed it.
David Harris
<ds.algorithms><fourier-analysis>
Truncated convolution algorithm
David Harris
# Truncated convolution algorithm

(Asked by: username_0 on 2012-08-15)

Suppose I have $n+1$-dimensional vectors $a$ and $b$. For each $i = 0, \dots, n$, I also have integers $0 \leq j\_0(i) \leq j\_1(i) \leq i$. I want to compute the following variant of a convolution:

$$
c\_i = \sum\_{j\_0(i) \leq j \leq j\_1(i)} a\_j b\_{i-j}
$$

If $j\_0(i) = 0, j\_1(i) = i$ for all $i$ this is a standard convolution, so you can do this via FFT in time $O(n \log n)$.

Are there any good algorithms for this when $j\_0, j\_1$ are arbitrary?

**Tags:** ds.algorithms, fourier-analysis
> **Comments:**
> **username_1**: You're out by one I think. Both $a_0$ and $a_n$ are potentially referenced which means $a$ must have n+1 elements.  
> **username_0**: @user10310 you're right, I fixed it.  

---

## 0 answers

