Polynomial Multiplication

Note that when you multiply two polynomials together, their coefficients are convolved. To see this, let $ p(x)$ denote the $ m$th-order polynomial

$\displaystyle p(x) = p_0 + p_1 x + p_2 x^2 + \cdots + p_m x^m
$

with coefficients $ p_i$, and let $ q(x)$ denote the $ n$th-order polynomial

$\displaystyle q(x) = q_0 + q_1 x + q_2 x^2 + \cdots + q_n x^n
$

with coefficients $ q_i$. Then we have [1]

\begin{eqnarray*}
p(x) q(x) &=& p_0 q_0 + (p_0 q_1 + p_1 q_0) x + (p_0 q_2 + p_1...
...\qquad\qquad\;
\mathop{+} p_{n+m-1} q_1 + p_{n+m} q_0) x^{n+m}.
\end{eqnarray*}

Denoting $ p(x) q(x)$ by

$\displaystyle r(x) \isdef p(x) q(x) = r_0 + r_1 x + r_2 x^2 + \cdots + r_{m+n} x^{m+n},
$

we have that the $ i$th coefficient can be expressed as

\begin{eqnarray*}
r_i &=& p_0 q_i + p_1 q_{i-1} + p_2 q_{i-2} + \cdots + p_{i-1}...
...=-\infty}^\infty p_j q_{i-j}\\
&\isdef & (p \circledast q)(i),
\end{eqnarray*}

where $ p_i$ and $ q_i$ are doubly infinite sequences, defined as zero for $ i<0$ and $ i>m,n$, respectively.


Next Section:
Multiplication of Decimal Numbers
Previous Section:
Graphical Convolution