 Polynomial multiplication

Polynomial multiplication combines coefficients by convolution. If $A(x)={\sum }_i{a}_i{x}^i$ and $B(x)={\sum }_j{b}_j{x}^j$, then the coefficient of $x^k$ in $AB$ is ${\sum }_{i+j=k}{a}_i{b}_j$.

For example, $(1+2x)(3-x)=3+5x-2x^2$. The coefficient rule follows from the distributive property and $x^i{x}^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.