SIMPLE MULTIVARIATE POLYNOMIAL MULTIPLICATION

We observe that polynomial evaluation and interpolation can be perform ed fast over a multidimensional grid (lattice), and we apply this obse rvation in order to devise a simple algorithm for multivariate polynom ial multiplication. Surprisingly, this simple idea enables us to impro ve the known algorithms for multivariate polynomial multiplication bas ed on the forward and backward application of Kronecker's map; in part icular, we decrease, by the factor log log N, the known upper bound on the arithmetic time-complexity of this computation (over any field of constants), provided that the degree d in each of the m variables is fixed, m grows to the infinity, and N = (d + 1)m.