12
$\begingroup$

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.

  • 0
    I believe you mean 'multinomials' if I'm not mistaken.2010-10-26
  • 0
    @ WWright - Dang spell check, thanks for the heads up!2010-10-26
  • 0
    @Hooked No problem, I just wish I could say something intelligible about your question :)2010-10-26
  • 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).2010-10-26
  • 3
    @Qiaochu, @Hooked: It's usually called the multi*dimensional* 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.2010-10-26
  • 0
    You can use kronecker substitution to convert the bivariate problem into a univariate.2011-02-07
  • 1
    @M.S. can you turn that comment into an answer? The wikipedia on the topic is woefully incomplete2011-02-08
  • 1
    check this link for the definition http://webcourse.cs.technion.ac.il/236649/Winter2007-2008/hw/WCFiles/ex3.pdf and these slides http://www.csd.uwo.ca/~eschost/publications/10-11/CS4424-lecture-1.pdf for examples.2011-02-08
  • 0
    @Rahul, why not posting that comment as answer? :)2012-08-13

1 Answers 1

3

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.