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}.$$

• «
• 1
• ...
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• ...
• 61
• »