Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I believe you mean 'multinomials' if I'm not mistaken. –  WWright Oct 26 '10 at 20:54
3  
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
3  
@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
1  
@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
1  
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

1 Answer 1

Community wiki answer so the question can be resolved:

As pointed out in the comments, this can be done using multidimensional FFT, with the exponents of the variables serving as coordinates.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.