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?
10
-
4$\begingroup$ (Assuming a commutative multiplication and cheap addition and subtraction) since arbitrary multiplication can be formed as a difference of squares, there should not be anything much faster (asympototically) than a general algorithm. If you have a specific domain or certain fixed parameters, there may be tweaks to the code that can help. Gerhard "What Size Is Your Problem?" Paseman, 2019.08.24. $\endgroup$– Gerhard PasemanCommented Aug 24, 2019 at 22:38
-
$\begingroup$ @GerhardPaseman can you prove so? (or if you already did that above, can you write it with big O notations/ give some upper limit that can't be crossed?) $\endgroup$– WiccanKarnakCommented Aug 24, 2019 at 22:41
-
4$\begingroup$ 4AB = (A+B)^2 - (A-B)^2. Gerhard "Don't Use This On Matrices" Paseman, 2019.08.24. $\endgroup$– Gerhard PasemanCommented Aug 24, 2019 at 23:07
-
1$\begingroup$ @Gerry Myerson: I suspect sie's wondering if that $O(n \log n)$ is provably optimal, or there is something between $O(n)$ and $O(n \log n)$ (e.g. $O(n \log \log n)$ or similar). That is, is there a proven optimal bound, and if so, what is it? $\endgroup$– The_SympathizerCommented Aug 25, 2019 at 0:10
-
1$\begingroup$ @The, could be, or it could be that OP was unaware of how close FFT is to best possible. I was just trying to figure out which. $\endgroup$– Gerry MyersonCommented Aug 25, 2019 at 0:24
|
Show 5 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
answered Aug 25, 2019 at 6:59
$\begingroup$
$\endgroup$
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.
