El uso de FFT en la multiplicación de multinomios

Question

Soy consciente de que se puede usar una Transformada rápida de Fourier (FFT) para tomar el coste de la multiplicación de dos polinomios de grado N de O $(N^2)$ a O $(N \ln N)$ (lo cual es una reducción asombrosa cuando se trata de grandes polinomios!). ¿Existe un procedimiento de transformación similar para los multinomios?

Me interesa el caso especial en el que el número de variables independientes es sólo dos, es decir. $h(x,y) = f(x,y)g(x,y)$ pero me encantaría leer sobre el procedimiento general.

Answer 1

La respuesta de la comunidad wiki para que la pregunta pueda ser resuelta:

Como se ha señalado en los comentarios, esto puede hacerse utilizando FFT multidimensional, con los exponentes de las variables sirviendo como coordenadas.