Convolutions, Polynomials and Flipped Kernels

Summary

This is a post about multiplying polynomials, convolution sums and the connection between them. Multiplying polynomials Suppose we want to multiply one polynomial by another: \[(3x^3+x^2+2x+1)\cdot(2x^2+6)\] This is basic middle-school math - we start by cross-multiplying: \[6x^5+2x^4+4x^3+2x^2+18x^3+6x^2+12x+6\] And then collect all the terms together by adding up the coefficients: \[6x^5+2x^4+22x^3+8x^2+12x+6\] Let's look at a slightly different way to achieve the same result. Instead of cross multiplying all terms and then adding up, we'll focus on what terms appear in the output, and for each such term - what its coefficients are going to be. This is easy to demonstrate with a table, where we lay out one polynomial horizontally and the other vertically. Note that we have to be explicit about the zero coefficient of x in the second polynomial: The diagonals that add up to each term in the output are highlighted. For example, to get the coefficient of x^3 in the output, we have to add up: The coefficient of x^3 in the first polynomial, multiplied by the constant (coefficient of x^0) in the second polynomial The coefficient of x^2 in the first polynomial, multiplied by the coefficient of in the second polynomial The coefficient of in the first polynomial, multiplied by the coefficients of x^2 in the second polynomial (if the second polynomial had a x^3 term, there would be another component to add) For what follows, let's move to a somewhat more abstract representation: a polynomial P can be represented as a sum of coefficients P_i multiplied by corresponding powers of x : \[P=\sum_{i}P_i x^i\] Suppose we have two polynomials, P and R. When we multiply them together, the resulting polynomial is S. Based on our insight from the table diagonals above, we can say that for each k: \[S_k=\sum_{i}P_i\cdot R_{k-i}\] And then the entire polynomial S is: \[S=\sum_{k} \left( \sum_{i}P_i\cdot R_{k-i}\right)x^k\] It's important to understand this formulation, since it's key to...