Simple multivariate polynomial multiplication (Q1346473): Difference between revisions

Let \(u= u(x_1, \dots, x_m)\) and \(v= v(x_1, \dots, x_m)\) be \(m\)-variate polynomials over a field \(F\) and let \(N= c^m\), where \(c\) is chosen so that \(c\geq 2\deg_{x_i} (u)+ 1,2 \deg_{x_i} (v)+ 1\) \((1\leq i\leq m)\). It is known that the product \(uv\) can be computed in time \(O(N \log N\log \log N)\). In this note it is shown that it can be computed in time \(O(N \log N)\), the bound already known to hold when \(F\) supports FFT at \(2^{\lceil \log_2 N\rceil}\).