0
$\begingroup$

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!

$\endgroup$

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.