Simple Multivariate Polynomial Multiplication

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

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).

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-93-003.pdf
Bibliographic Notes

ICSI Technical Report TR-93-003

Abbreviated Authors

V. Pan

ICSI Publication Type

Technical Report