Efficient Polynomial Multiplication

Computing polynomial products can be implemented efficiently if we rewrite the more brute force multiplications using convolution. We note first that the new coefficients are given as

$$ \begin{split} \delta_0=&\alpha_0\beta_0\\ \delta_1=&\alpha_1\beta_0+\alpha_0\beta_1\\ \delta_2=&\alpha_0\beta_2+\alpha_1\beta_1+\alpha_2\beta_0\\ \delta_3=&\alpha_1\beta_2+\alpha_2\beta_1+\alpha_0\beta_3\\ \delta_4=&\alpha_2\beta_2+\alpha_1\beta_3\\ \delta_5=&\alpha_2\beta_3.\\ \end{split} $$

We note that \( \alpha_i=0 \) except for \( i\in \left\{0,1,2\right\} \) and \( \beta_i=0 \) except for \( i\in\left\{0,1,2,3\right\} \).

We can then rewrite the coefficients \( \delta_j \) using a discrete convolution as

$$ \delta_j = \sum_{i=-\infty}^{i=\infty}\alpha_i\beta_{j-i}=(\alpha * \beta)_j, $$

or as a double sum with restriction \( l=i+j \)

$$ \delta_l = \sum_{ij}\alpha_i\beta_{j}. $$