Simple Multivariate Polynomial Multiplication
Title | Simple Multivariate Polynomial Multiplication |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Pan, V. |
Other Numbers | 791 |
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). |
URL | http://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 |