Convolutions, Polynomials and Flipped Kernels

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 h ... Read full article.