FFT is a quick algorithm for multiplying two polynomials, but given it's a square (i.e. multiplying the polynomial with itself) can we find something better?



Process quicker than Fourier for squares of polynomials
As requested, here is an answer.


$$2(AB + BA) = (A+B)^2 - (A-B)^2$$
Is an identity that holds in rings in general. When the ring multiplication is commutative and one can divide by 4 nicely, this gives a means of multiplying $A$ and $B$ in terms of adding, subtracting, and two squaring operations. So any fast routine for squaring in the right kind of ring leads to a fast multiplication algorithm. It should be clear how fast multiplication leads to fast squaring.


Back in another lifetime, I looked at implementing the above using programmable logic chips to produce a fast multiplier. (The basic idea was that minimizing the logic for squaring binary integers might lead to a smaller circuit depth.) The result did not gain much for 16 bit integers. Nowadays 64 bit arithmetic is "kept under the hood" meaning multiplication is seen as fast enough, so this approach of reducing circuit depth by squaring is unlikely to be practical.


In the case that your domain is restricted, so that you are squaring a small class of polynomials, you might find a more optimal circuit/method, especially if the polynomials are multiplicatively generated, or if you have a fast transform like a logarithm/exponential pair available. At present, I am not aware of anything that in practice is much faster than FFT for squaring.


Gerhard "It's All About The Speed" Paseman, 2019.08.24.


