Process quicker than Fourier for squares of polynomials

Assuming the question is over $\mathbb{R}$, squaring the polynomial $a(x)=a_0+a_1x+\cdots+a_n x^n$ is essentially the (noncyclic) convolution of the vector $$(a_0,a_1,\ldots,a_n,0,\ldots,0)\in \mathbb{R}^{2n+1}$$ with itself to obtain the coefficients of the square polynomial. Of course convolution can be carried out efficiently with an FFT.

There are no results that I am aware of for faster than $O(n \log n)$ FFT. If you have a special structure to your polynomial coefficients, there might be shortcuts.

If the fourier transform is sparse, there are recent results you can try and use. You may start at this link here.

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.