= Polynomial multiplication
<Polynomial multiplication> combines coefficients by <convolution>. If $A(x)=\sum_i a_ix^i$ and $B(x)=\sum_jb_jx^j$, then the coefficient of $x^k$ in $AB$ is $\sum_{i+j=k}a_ib_j$.
For example, $(1+2x)(3-x)=3+5x-2x^2$. The coefficient rule follows from the <distributive property> and $x^ix^j=x^{i+j}$. The school method takes $O(mn)$ coefficient operations for $m,n$ coefficients; <Karatsuba multiplication> and <Fast Fourier transforms> give faster methods for large inputs. Over exact coefficient <rings>, transform methods must still recover exact coefficients, rather than accepting uncontrolled rounding.
Back to article page
