I'm having some trouble figuring out how to use Fast Fourier Transforms to multiply multivariate polynomials. I'm writing a program that intended to expand a large polynomial made of lots of small factors.
For example, here's a (very small) polynomial that the program might be asked to expand:
(x1 - x2 - x3 + y1 - y2)*(x1 - x2)*(x1 - x3)*(x2 + x3 - y1 + y2)*(x2 + x3)*(x2 - x3)*(y1 - y2)
I'm familiar with the use of the numpy.fft packages to multiply single-variable polynomials, passing each polynomial in as an array of coefficients.
For example, the polynomial
x^3 + 5x^2 + 6 would be represented as
[6, 0, 5, 1], and the multiplication would be calculated with:
ifft( fft(polynomial1) * fft(polynomial2))
ifft() is an inverse fourier transform
My question is, how can I best use Fourier transforms to quickly expand a polynomial with a high number of variables like the ones I am working with.
I checked out this previous question which covers the same topic, but I don't really understand how the result of the transform is converted back into a polynomial.
Can the method in that question be applied to a polynomial with such a high number of variables? Is this even really the best way to be doing this? Any help would be much appreciated!