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))

Note: 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!


Your Answer

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

Browse other questions tagged or ask your own question.