Simple Multivariate Polynomial Multiplication

TitleSimple Multivariate Polynomial Multiplication
Publication TypeTechnical Report
Year of Publication1993
AuthorsPan, V.
Other Numbers791

We observe that polynomial evaluation and interpolation can be performed fast over a multidimensional grid (lattice), and we apply this observation in order to obtain the boundsM(c,m) ? (c^m)(1 + m + 1.5m + 2(log subscript 2)c)over the fields of constants supporting FFT on c points, c being a power of 2, andM (c, m) = 0[N log N log log c],over any field, where N = c^m, and M (c, m) denotes the number of arithmetic operations required in order to multiply (over any field F) a pair of m-variate polynomials whose product has degree at most c - 1 in each variable, so that M (c, m) = 0(N log N) if c=0(1), m ? ? (over any field F), versus the known bound of O (N log N log log N).

Bibliographic Notes

ICSI Technical Report TR-93-003

Abbreviated Authors

V. Pan

ICSI Publication Type

Technical Report