I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying?

For example, if you are multiplying $A(x) = 1 + 2x + 6x^2$ and $B(x) = 4 + 5x + 3x^2$ such that you get $C(x) = A(x) \cdot B(x) = 4 + 5x + 3x^2 + 8x + 10x^2 + 6x^3 + 24x^2 + 30x^3 + 18x^4$ without going directly to the simplified answer?

Furthermore, is it possible to use FFT to do this expanded form multiplication in $O(n\,log\,n)$ time? If so, can you show me how to apply FFT to this scenario?

  • 1
    $\begingroup$ Why would you want to do this? $\endgroup$ – Yuval Filmus Sep 22 '13 at 4:23

The trivial algorithm that multiplies every monomial in $A$ by every monomial in $B$ takes time $O(|A| \cdot |B|)$ (where $|A|$ is the number of monomials in $A$ or $\deg A + 1$, depending on the representation), which is the same order of magnitude as the size of the output, and so optimal. You only need FFT if you want to actually compute the product $AB$. In particular, there is no way to compute your function in time $O(n\log n)$, simply because the length of the output is $\Omega(n^2)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.