I am interested in computing a particular sum, namely: $\sum_{j=l}^{m}(i-j)f_{i-j}g_j$.
I have two polynomials defined $f(x)$ and $g(x)$. The idea is to compute the sum above by writing two new polynomials: $F(x)=\sum^{r-l}_{k=0} k f_k x^k$ and $G(x)=\sum_{j=0}^{m-l}g_{j+l}x^j$.
We then use FFT to compute $H(x)=F(x)G(x)$, and the monomial [$x^{i-l}$]$H(x)$ will have coefficients equal to $\sum_{j=l}^{m}(i-j)f_{i-j}g_j$.
Can anyone help me understand this reduction? I can get as far as understanding that we write the convolution formula: $\sum^{i-l}_{a=0}af_ag_{i-l+l-a}$ where the terms cancel and we are left with $\sum^{i-l}_{a=0}af_ag_{i-a}$.
I believe the relation $m=floor(\frac{l+r}{2})$ may also be necessary to include.
The paper that does this is available here https://arxiv.org/abs/1807.11597