# Use of FFT in the multiplication of multinomials

I'm aware that one can use a Fast Fourier Transform (FFT) to take the cost of multiplication of two polynomials of degree N from O$(N^2)$ to O$(N \ln N)$ (which is an amazing reduction when dealing with large polynomials!). Does a similar transformation procedure exist for multinomials?

I'm interested in the special case where the number of independent variables is only two, ie. $h(x,y) = f(x,y)g(x,y)$, but I'd love to read up on the general procedure.

-
I believe you mean 'multinomials' if I'm not mistaken. –  WWright Oct 26 '10 at 20:54
The word you want is still "polynomial" (maybe "multivariate polynomial" if you want to be precise) and as far as I know the technique you want is still FFT, just in more variables (I think Googling "multivariate FFT" might help you out). –  Qiaochu Yuan Oct 26 '10 at 21:30
@Qiaochu, @Hooked: It's usually called the multidimensional FFT in $n$ dimensions, and of course it's just the standard FFT run $n$ times in different directions. It helps to think of the data as an $n$-dimensional grid on which you run the FFT once on each row, then once on each column, and so on. –  Rahul Oct 26 '10 at 22:29
@M.S. can you turn that comment into an answer? The wikipedia on the topic is woefully incomplete –  Hooked Feb 8 '11 at 2:17
check this link for the definition webcourse.cs.technion.ac.il/236649/Winter2007-2008/hw/WCFiles/… and these slides csd.uwo.ca/~eschost/publications/10-11/CS4424-lecture-1.pdf for examples. –  user2468 Feb 8 '11 at 4:18